2 regcomp.c - TRE POSIX compatible regex compilation functions.
4 Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi>
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions
11 1. Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
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.
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.
43 /***********************************************************************
45 ***********************************************************************/
54 tre_ctype_t *neg_classes;
59 /***********************************************************************
60 from tre-ast.c and tre-ast.h
61 ***********************************************************************/
63 /* The different AST node types. */
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. */
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)
84 /* A generic AST node. All AST nodes consist of this node on the top
85 level with `obj' pointing to the actual content. */
87 tre_ast_type_t type; /* Type of the node. */
88 void *obj; /* Pointer to actual node. */
93 tre_pos_and_tags_t *firstpos;
94 tre_pos_and_tags_t *lastpos;
98 /* A "literal" node. These are created for assertions, back references,
99 tags, matching parameter settings, and all expressions that match one
106 tre_ctype_t *neg_classes;
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). */
114 tre_ast_node_t *left;
115 tre_ast_node_t *right;
118 /* An "iteration" node. These are created for the "*", "+", "?", and "{m,n}"
121 /* Subexpression to match. */
123 /* Minimum number of consecutive matches. */
125 /* Maximum number of consecutive matches. */
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;
133 /* An "union" node. These are created for the "|" operator. */
135 tre_ast_node_t *left;
136 tre_ast_node_t *right;
140 static tre_ast_node_t *
141 tre_ast_new_node(tre_mem_t mem, int type, void *obj)
143 tre_ast_node_t *node = tre_mem_calloc(mem, sizeof *node);
149 node->submatch_id = -1;
153 static tre_ast_node_t *
154 tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position)
156 tre_ast_node_t *node;
159 lit = tre_mem_calloc(mem, sizeof *lit);
160 node = tre_ast_new_node(mem, LITERAL, lit);
163 lit->code_min = code_min;
164 lit->code_max = code_max;
165 lit->position = position;
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)
172 tre_ast_node_t *node;
173 tre_iteration_t *iter;
175 iter = tre_mem_calloc(mem, sizeof *iter);
176 node = tre_ast_new_node(mem, ITERATION, iter);
182 iter->minimal = minimal;
183 node->num_submatches = arg->num_submatches;
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)
190 tre_ast_node_t *node;
195 un = tre_mem_calloc(mem, sizeof *un);
196 node = tre_ast_new_node(mem, UNION, un);
201 node->num_submatches = left->num_submatches + right->num_submatches;
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)
208 tre_ast_node_t *node;
209 tre_catenation_t *cat;
213 cat = tre_mem_calloc(mem, sizeof *cat);
214 node = tre_ast_new_node(mem, CATENATION, cat);
219 node->num_submatches = left->num_submatches + right->num_submatches;
224 /***********************************************************************
225 from tre-stack.c and tre-stack.h
226 ***********************************************************************/
228 typedef struct tre_stack_rec tre_stack_t;
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. */
235 tre_stack_new(int size, int max_size, int increment);
237 /* Frees the stack object. */
239 tre_stack_destroy(tre_stack_t *s);
241 /* Returns the current number of objects in the stack. */
243 tre_stack_num_objects(tre_stack_t *s);
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)
252 declare_pushf(voidptr, void *);
253 declare_pushf(int, int);
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
258 #define declare_popf(typetag, type) \
259 static type tre_stack_pop_ ## typetag(tre_stack_t *s)
261 declare_popf(voidptr, void *);
262 declare_popf(int, int);
264 /* Just to save some typing. */
265 #define STACK_PUSH(s, typetag, value) \
268 status = tre_stack_push_ ## typetag(s, value); \
270 while (/*CONSTCOND*/0)
272 #define STACK_PUSHX(s, typetag, value) \
274 status = tre_stack_push_ ## typetag(s, value); \
275 if (status != REG_OK) \
279 #define STACK_PUSHR(s, typetag, value) \
281 reg_errcode_t _status; \
282 _status = tre_stack_push_ ## typetag(s, value); \
283 if (_status != REG_OK) \
287 union tre_stack_item {
292 struct tre_stack_rec {
297 union tre_stack_item *stack;
302 tre_stack_new(int size, int max_size, int increment)
306 s = xmalloc(sizeof(*s));
309 s->stack = xmalloc(sizeof(*s->stack) * size);
310 if (s->stack == NULL)
316 s->max_size = max_size;
317 s->increment = increment;
324 tre_stack_destroy(tre_stack_t *s)
331 tre_stack_num_objects(tre_stack_t *s)
337 tre_stack_push(tre_stack_t *s, union tre_stack_item value)
339 if (s->ptr < s->size)
341 s->stack[s->ptr] = value;
346 if (s->size >= s->max_size)
352 union tre_stack_item *new_buffer;
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)
362 assert(new_size > s->size);
364 s->stack = new_buffer;
365 tre_stack_push(s, value);
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); \
378 define_pushf(int, int)
379 define_pushf(voidptr, void *)
381 #define define_popf(typetag, type) \
382 declare_popf(typetag, type) { \
383 return s->stack[--s->ptr].typetag ## _value; \
386 define_popf(int, int)
387 define_popf(voidptr, void *)
390 /***********************************************************************
391 from tre-parse.c and tre-parse.h
392 ***********************************************************************/
396 /* Memory allocator. The AST is allocated using this. */
398 /* Stack used for keeping track of regexp syntax. */
400 /* The parsed node after a parse function returns. */
402 /* Position in the regexp pattern after a parse function returns. */
404 /* The first character of the regexp. */
406 /* Current submatch ID. */
408 /* Current position (number of literal). */
410 /* The highest back reference or -1 if none seen so far. */
412 /* Compilation flags. */
416 /* Some macros for expanding \w, \s, etc. */
417 static const struct {
419 const char *expansion;
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:]]"},
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)
434 for (i = 0; tre_macros[i].c && tre_macros[i].c != *s; i++);
435 return tre_macros[i].expansion;
439 tre_compare_lit(const void *a, const void *b)
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;
454 static tre_literal_t *tre_new_lit(struct literals *p)
457 if (p->len >= p->cap) {
461 a = xrealloc(p->a, p->cap * sizeof *p->a);
467 *a = tre_mem_calloc(p->mem, sizeof **a);
471 static int add_icase_literals(struct literals *ls, int min, int max)
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;
491 lit = tre_new_lit(ls);
502 /* Maximum number of character classes in a negated bracket expression. */
503 #define MAX_NEG_CLASSES 64
508 tre_ctype_t a[MAX_NEG_CLASSES];
511 // TODO: parse bracket into a set of non-overlapping [lo,hi] ranges
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
521 Coll = '[.' coll_single '.]' | '[.' coll_multi '.]' | '[.' Meta '.]'
522 Eqclass = '[=' coll_single '=]' | '[=' coll_multi '=]'
523 Chclass = '[:' class ':]'
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 '['
531 static reg_errcode_t parse_bracket_terms(tre_parse_ctx_t *ctx, const char *s, struct literals *ls, struct neg *neg)
533 const char *start = s;
541 len = mbtowc(&wc, s, -1);
543 return *s ? REG_BADPAT : REG_EBRACK;
544 if (*s == ']' && s != start) {
548 if (*s == '-' && s != start && s[1] != ']' &&
549 /* extension: [a-z--@] is accepted as [a-z]|[--@] */
550 (s[1] != '-' || s[2] == ']'))
552 if (*s == '[' && (s[1] == '.' || s[1] == '='))
553 /* collating symbols and equivalence classes are not supported */
555 if (*s == '[' && s[1] == ':') {
556 char tmp[CHARCLASS_NAME_MAX+1];
558 for (len=0; len < CHARCLASS_NAME_MAX && s[len]; len++) {
562 class = tre_ctype(tmp);
566 if (!class || s[len+1] != ']')
574 if (*s == '-' && s[1] != ']') {
576 len = mbtowc(&wc, s, -1);
578 /* XXX - Should use collation order instead of
579 encoding values in character ranges. */
580 if (len <= 0 || min > max)
586 if (class && neg->negate) {
587 if (neg->len >= MAX_NEG_CLASSES)
589 neg->a[neg->len++] = class;
591 tre_literal_t *lit = tre_new_lit(ls);
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))
613 static reg_errcode_t parse_bracket(tre_parse_ctx_t *ctx, const char *s)
615 int i, max, min, negmax, negmin;
616 tre_ast_node_t *node = 0, *n;
626 ls.a = xmalloc(ls.cap * sizeof *ls.a);
630 neg.negate = *s == '^';
634 err = parse_bracket_terms(ctx, s, &ls, &neg);
636 goto parse_bracket_done;
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);
645 goto parse_bracket_done;
647 lit->code_min = TRE_CHAR_MAX+1;
648 lit->code_max = TRE_CHAR_MAX+1;
650 /* negated classes */
652 nc = tre_mem_alloc(ctx->mem, (neg.len+1)*sizeof *neg.a);
655 goto parse_bracket_done;
657 memcpy(nc, neg.a, neg.len*sizeof *neg.a);
662 /* Build a union of the items in the array, negated if necessary. */
664 for (i = 0; i < ls.len; i++) {
671 negmin = MAX(max + 1, negmin);
675 lit->code_min = negmin;
676 lit->code_max = negmax;
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);
696 static const char *parse_dup_count(const char *s, int *n)
703 *n = 10 * *n + (*s - '0');
705 if (!isdigit(*s) || *n > RE_DUP_MAX)
711 static reg_errcode_t parse_dup(tre_parse_ctx_t *ctx, const char *s)
715 s = parse_dup_count(s, &min);
717 s = parse_dup_count(s+1, &max);
722 (max < min && max >= 0) ||
726 (!(ctx->cflags & REG_EXTENDED) && *s++ != '\\') ||
731 if (min == 0 && max == 0)
732 ctx->n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
734 ctx->n = tre_ast_new_iter(ctx->mem, ctx->n, min, max, 0);
741 static int hexval(unsigned c)
743 if (c-'0'<10) return c-'0';
745 if (c-'a'<6) return c-'a'+10;
749 static reg_errcode_t marksub(tre_parse_ctx_t *ctx, tre_ast_node_t *node, int subid)
751 if (node->submatch_id >= 0) {
752 tre_ast_node_t *n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
755 n = tre_ast_new_catenation(ctx->mem, n, node);
758 n->num_submatches = node->num_submatches;
761 node->submatch_id = subid;
762 node->num_submatches++;
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 '\}'
774 (leading ^ and trailing $ in a sub expr may be an anchor or literal as well)
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 '}'
782 (a*+?, ^*, $+, \X, {, (|a) are unspecified)
785 static reg_errcode_t parse_atom(tre_parse_ctx_t *ctx, const char *s)
787 int len, ere = ctx->cflags & REG_EXTENDED;
789 tre_ast_node_t *node;
793 return parse_bracket(ctx, s+1);
795 p = tre_expand_macro(s+1);
797 /* assume \X expansion is a single atom */
798 reg_errcode_t err = parse_atom(ctx, p);
802 /* extensions: \b, \B, \<, \>, \xHH \x{HHHH} */
807 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_WB, -1);
810 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_WB_NEG, -1);
813 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_BOW, -1);
816 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_EOW, -1);
826 for (i=0; i<len && v<0x110000; i++) {
837 node = tre_ast_new_literal(ctx->mem, v, v, ctx->position);
842 if (!ere && (unsigned)*s-'1' < 9) {
845 node = tre_ast_new_literal(ctx->mem, BACKREF, val, ctx->position);
846 ctx->max_backref = MAX(val, ctx->max_backref);
848 /* extension: accept unknown escaped char
857 if (ctx->cflags & REG_NEWLINE) {
858 tre_ast_node_t *tmp1, *tmp2;
859 tmp1 = tre_ast_new_literal(ctx->mem, 0, '\n'-1, ctx->position++);
860 tmp2 = tre_ast_new_literal(ctx->mem, '\n'+1, TRE_CHAR_MAX, ctx->position++);
862 node = tre_ast_new_union(ctx->mem, tmp1, tmp2);
866 node = tre_ast_new_literal(ctx->mem, 0, TRE_CHAR_MAX, ctx->position++);
871 /* '^' has a special meaning everywhere in EREs, and at beginning of BRE. */
872 if (!ere && s != ctx->re)
874 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_BOL, -1);
878 /* '$' is special everywhere in EREs, and in the end of the string in BREs. */
881 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_EOL, -1);
892 node = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
896 len = mbtowc(&wc, s, -1);
899 if (ctx->cflags & REG_ICASE && (tre_isupper(wc) || tre_islower(wc))) {
900 tre_ast_node_t *tmp1, *tmp2;
901 /* multiple opposite case characters are not supported */
902 tmp1 = tre_ast_new_literal(ctx->mem, tre_toupper(wc), tre_toupper(wc), ctx->position);
903 tmp2 = tre_ast_new_literal(ctx->mem, tre_tolower(wc), tre_tolower(wc), ctx->position);
905 node = tre_ast_new_union(ctx->mem, tmp1, tmp2);
909 node = tre_ast_new_literal(ctx->mem, wc, wc, ctx->position);
922 #define PUSHPTR(err, s, v) do { \
923 if ((err = tre_stack_push_voidptr(s, v)) != REG_OK) \
927 #define PUSHINT(err, s, v) do { \
928 if ((err = tre_stack_push_int(s, v)) != REG_OK) \
932 static reg_errcode_t tre_parse(tre_parse_ctx_t *ctx)
934 tre_ast_node_t *nbranch=0, *nunion=0;
935 int ere = ctx->cflags & REG_EXTENDED;
936 const char *s = ctx->re;
940 tre_stack_t *stack = ctx->stack;
942 PUSHINT(err, stack, subid++);
944 if ((!ere && *s == '\\' && s[1] == '(') ||
945 (ere && *s == '(')) {
946 PUSHPTR(err, stack, nunion);
947 PUSHPTR(err, stack, nbranch);
948 PUSHINT(err, stack, subid++);
953 nbranch = nunion = 0;
956 if ((!ere && *s == '\\' && s[1] == ')') ||
957 (ere && *s == ')' && depth)) {
958 ctx->n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
962 err = parse_atom(ctx, s);
969 /* extension: repetitions are accepted after an empty node
970 eg. (+), ^*, a$?, a|{2} */
984 ctx->n = tre_ast_new_iter(ctx->mem, ctx->n, min, max, 0);
987 /* extension: multiple consecutive *+?{,} is unspecified,
988 but (a+)+ has to be supported so accepting a++ makes
989 sense, note however that the RE_DUP_MAX limit can be
990 circumvented: (a{255}){255} uses a lot of memory.. */
993 if (ere || s[1] != '{')
1001 err = parse_dup(ctx, s+1);
1008 nbranch = tre_ast_new_catenation(ctx->mem, nbranch, ctx->n);
1009 if ((ere && *s == '|') ||
1010 (ere && *s == ')' && depth) ||
1011 (!ere && *s == '\\' && s[1] == ')') ||
1013 /* extension: empty branch is unspecified (), (|a), (a|)
1014 here they are not rejected but match on empty string */
1016 nunion = tre_ast_new_union(ctx->mem, nunion, nbranch);
1020 if (!depth) return REG_EPAREN;
1022 } else if (c == ')')
1025 err = marksub(ctx, nunion, tre_stack_pop_int(stack));
1028 if (!c && depth<0) {
1029 ctx->submatch_id = subid;
1034 nbranch = tre_stack_pop_voidptr(stack);
1035 nunion = tre_stack_pop_voidptr(stack);
1044 /***********************************************************************
1046 ***********************************************************************/
1051 - Fix tre_ast_to_tnfa() to recurse using a stack instead of recursive
1056 Algorithms to setup tags so that submatch addressing can be done.
1060 /* Inserts a catenation node to the root of the tree given in `node'.
1061 As the left child a new tag with number `tag_id' to `node' is added,
1062 and the right child is the old root. */
1063 static reg_errcode_t
1064 tre_add_tag_left(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1066 tre_catenation_t *c;
1068 c = tre_mem_alloc(mem, sizeof(*c));
1071 c->left = tre_ast_new_literal(mem, TAG, tag_id, -1);
1072 if (c->left == NULL)
1074 c->right = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1075 if (c->right == NULL)
1078 c->right->obj = node->obj;
1079 c->right->type = node->type;
1080 c->right->nullable = -1;
1081 c->right->submatch_id = -1;
1082 c->right->firstpos = NULL;
1083 c->right->lastpos = NULL;
1084 c->right->num_tags = 0;
1086 node->type = CATENATION;
1090 /* Inserts a catenation node to the root of the tree given in `node'.
1091 As the right child a new tag with number `tag_id' to `node' is added,
1092 and the left child is the old root. */
1093 static reg_errcode_t
1094 tre_add_tag_right(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1096 tre_catenation_t *c;
1098 c = tre_mem_alloc(mem, sizeof(*c));
1101 c->right = tre_ast_new_literal(mem, TAG, tag_id, -1);
1102 if (c->right == NULL)
1104 c->left = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1105 if (c->left == NULL)
1108 c->left->obj = node->obj;
1109 c->left->type = node->type;
1110 c->left->nullable = -1;
1111 c->left->submatch_id = -1;
1112 c->left->firstpos = NULL;
1113 c->left->lastpos = NULL;
1114 c->left->num_tags = 0;
1116 node->type = CATENATION;
1122 ADDTAGS_AFTER_ITERATION,
1123 ADDTAGS_AFTER_UNION_LEFT,
1124 ADDTAGS_AFTER_UNION_RIGHT,
1125 ADDTAGS_AFTER_CAT_LEFT,
1126 ADDTAGS_AFTER_CAT_RIGHT,
1127 ADDTAGS_SET_SUBMATCH_END
1128 } tre_addtags_symbol_t;
1137 /* Go through `regset' and set submatch data for submatches that are
1140 tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag)
1144 for (i = 0; regset[i] >= 0; i++)
1146 int id = regset[i] / 2;
1147 int start = !(regset[i] % 2);
1149 tnfa->submatch_data[id].so_tag = tag;
1151 tnfa->submatch_data[id].eo_tag = tag;
1157 /* Adds tags to appropriate locations in the parse tree in `tree', so that
1158 subexpressions marked for submatch addressing can be traced. */
1159 static reg_errcode_t
1160 tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree,
1163 reg_errcode_t status = REG_OK;
1164 tre_addtags_symbol_t symbol;
1165 tre_ast_node_t *node = tree; /* Tree node we are currently looking at. */
1166 int bottom = tre_stack_num_objects(stack);
1167 /* True for first pass (counting number of needed tags) */
1168 int first_pass = (mem == NULL || tnfa == NULL);
1169 int *regset, *orig_regset;
1170 int num_tags = 0; /* Total number of tags. */
1171 int num_minimals = 0; /* Number of special minimal tags. */
1172 int tag = 0; /* The tag that is to be added next. */
1173 int next_tag = 1; /* Next tag to use after this one. */
1174 int *parents; /* Stack of submatches the current submatch is
1176 int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */
1177 tre_tag_states_t *saved_states;
1179 tre_tag_direction_t direction = TRE_TAG_MINIMIZE;
1183 tnfa->minimal_tags[0] = -1;
1186 regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2));
1190 orig_regset = regset;
1192 parents = xmalloc(sizeof(*parents) * (tnfa->num_submatches + 1));
1193 if (parents == NULL)
1200 saved_states = xmalloc(sizeof(*saved_states) * (tnfa->num_submatches + 1));
1201 if (saved_states == NULL)
1210 for (i = 0; i <= tnfa->num_submatches; i++)
1211 saved_states[i].tag = -1;
1214 STACK_PUSH(stack, voidptr, node);
1215 STACK_PUSH(stack, int, ADDTAGS_RECURSE);
1217 while (tre_stack_num_objects(stack) > bottom)
1219 if (status != REG_OK)
1222 symbol = (tre_addtags_symbol_t)tre_stack_pop_int(stack);
1226 case ADDTAGS_SET_SUBMATCH_END:
1228 int id = tre_stack_pop_int(stack);
1231 /* Add end of this submatch to regset. */
1232 for (i = 0; regset[i] >= 0; i++);
1233 regset[i] = id * 2 + 1;
1236 /* Pop this submatch from the parents stack. */
1237 for (i = 0; parents[i] >= 0; i++);
1238 parents[i - 1] = -1;
1242 case ADDTAGS_RECURSE:
1243 node = tre_stack_pop_voidptr(stack);
1245 if (node->submatch_id >= 0)
1247 int id = node->submatch_id;
1251 /* Add start of this submatch to regset. */
1252 for (i = 0; regset[i] >= 0; i++);
1258 for (i = 0; parents[i] >= 0; i++);
1259 tnfa->submatch_data[id].parents = NULL;
1262 int *p = xmalloc(sizeof(*p) * (i + 1));
1265 status = REG_ESPACE;
1268 assert(tnfa->submatch_data[id].parents == NULL);
1269 tnfa->submatch_data[id].parents = p;
1270 for (i = 0; parents[i] >= 0; i++)
1276 /* Add end of this submatch to regset after processing this
1278 STACK_PUSHX(stack, int, node->submatch_id);
1279 STACK_PUSHX(stack, int, ADDTAGS_SET_SUBMATCH_END);
1286 tre_literal_t *lit = node->obj;
1288 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1293 /* Regset is not empty, so add a tag before the
1294 literal or backref. */
1297 status = tre_add_tag_left(mem, node, tag);
1298 tnfa->tag_directions[tag] = direction;
1299 if (minimal_tag >= 0)
1301 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1302 tnfa->minimal_tags[i] = tag;
1303 tnfa->minimal_tags[i + 1] = minimal_tag;
1304 tnfa->minimal_tags[i + 2] = -1;
1308 tre_purge_regset(regset, tnfa, tag);
1323 assert(!IS_TAG(lit));
1329 tre_catenation_t *cat = node->obj;
1330 tre_ast_node_t *left = cat->left;
1331 tre_ast_node_t *right = cat->right;
1332 int reserved_tag = -1;
1335 /* After processing right child. */
1336 STACK_PUSHX(stack, voidptr, node);
1337 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_RIGHT);
1339 /* Process right child. */
1340 STACK_PUSHX(stack, voidptr, right);
1341 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1343 /* After processing left child. */
1344 STACK_PUSHX(stack, int, next_tag + left->num_tags);
1345 if (left->num_tags > 0 && right->num_tags > 0)
1347 /* Reserve the next tag to the right child. */
1348 reserved_tag = next_tag;
1351 STACK_PUSHX(stack, int, reserved_tag);
1352 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_LEFT);
1354 /* Process left child. */
1355 STACK_PUSHX(stack, voidptr, left);
1356 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1362 tre_iteration_t *iter = node->obj;
1366 STACK_PUSHX(stack, int, regset[0] >= 0 || iter->minimal);
1370 STACK_PUSHX(stack, int, tag);
1371 STACK_PUSHX(stack, int, iter->minimal);
1373 STACK_PUSHX(stack, voidptr, node);
1374 STACK_PUSHX(stack, int, ADDTAGS_AFTER_ITERATION);
1376 STACK_PUSHX(stack, voidptr, iter->arg);
1377 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1379 /* Regset is not empty, so add a tag here. */
1380 if (regset[0] >= 0 || iter->minimal)
1385 status = tre_add_tag_left(mem, node, tag);
1387 tnfa->tag_directions[tag] = TRE_TAG_MAXIMIZE;
1389 tnfa->tag_directions[tag] = direction;
1390 if (minimal_tag >= 0)
1392 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1393 tnfa->minimal_tags[i] = tag;
1394 tnfa->minimal_tags[i + 1] = minimal_tag;
1395 tnfa->minimal_tags[i + 2] = -1;
1399 tre_purge_regset(regset, tnfa, tag);
1407 direction = TRE_TAG_MINIMIZE;
1412 tre_union_t *uni = node->obj;
1413 tre_ast_node_t *left = uni->left;
1414 tre_ast_node_t *right = uni->right;
1420 left_tag = next_tag;
1421 right_tag = next_tag + 1;
1426 right_tag = next_tag;
1429 /* After processing right child. */
1430 STACK_PUSHX(stack, int, right_tag);
1431 STACK_PUSHX(stack, int, left_tag);
1432 STACK_PUSHX(stack, voidptr, regset);
1433 STACK_PUSHX(stack, int, regset[0] >= 0);
1434 STACK_PUSHX(stack, voidptr, node);
1435 STACK_PUSHX(stack, voidptr, right);
1436 STACK_PUSHX(stack, voidptr, left);
1437 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT);
1439 /* Process right child. */
1440 STACK_PUSHX(stack, voidptr, right);
1441 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1443 /* After processing left child. */
1444 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT);
1446 /* Process left child. */
1447 STACK_PUSHX(stack, voidptr, left);
1448 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1450 /* Regset is not empty, so add a tag here. */
1456 status = tre_add_tag_left(mem, node, tag);
1457 tnfa->tag_directions[tag] = direction;
1458 if (minimal_tag >= 0)
1460 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1461 tnfa->minimal_tags[i] = tag;
1462 tnfa->minimal_tags[i + 1] = minimal_tag;
1463 tnfa->minimal_tags[i + 2] = -1;
1467 tre_purge_regset(regset, tnfa, tag);
1476 if (node->num_submatches > 0)
1478 /* The next two tags are reserved for markers. */
1488 if (node->submatch_id >= 0)
1491 /* Push this submatch on the parents stack. */
1492 for (i = 0; parents[i] >= 0; i++);
1493 parents[i] = node->submatch_id;
1494 parents[i + 1] = -1;
1497 break; /* end case: ADDTAGS_RECURSE */
1499 case ADDTAGS_AFTER_ITERATION:
1503 node = tre_stack_pop_voidptr(stack);
1506 node->num_tags = ((tre_iteration_t *)node->obj)->arg->num_tags
1507 + tre_stack_pop_int(stack);
1512 minimal = tre_stack_pop_int(stack);
1513 enter_tag = tre_stack_pop_int(stack);
1515 minimal_tag = enter_tag;
1521 direction = TRE_TAG_MINIMIZE;
1523 direction = TRE_TAG_MAXIMIZE;
1528 case ADDTAGS_AFTER_CAT_LEFT:
1530 int new_tag = tre_stack_pop_int(stack);
1531 next_tag = tre_stack_pop_int(stack);
1539 case ADDTAGS_AFTER_CAT_RIGHT:
1540 node = tre_stack_pop_voidptr(stack);
1542 node->num_tags = ((tre_catenation_t *)node->obj)->left->num_tags
1543 + ((tre_catenation_t *)node->obj)->right->num_tags;
1546 case ADDTAGS_AFTER_UNION_LEFT:
1547 /* Lift the bottom of the `regset' array so that when processing
1548 the right operand the items currently in the array are
1549 invisible. The original bottom was saved at ADDTAGS_UNION and
1550 will be restored at ADDTAGS_AFTER_UNION_RIGHT below. */
1551 while (*regset >= 0)
1555 case ADDTAGS_AFTER_UNION_RIGHT:
1557 int added_tags, tag_left, tag_right;
1558 tre_ast_node_t *left = tre_stack_pop_voidptr(stack);
1559 tre_ast_node_t *right = tre_stack_pop_voidptr(stack);
1560 node = tre_stack_pop_voidptr(stack);
1561 added_tags = tre_stack_pop_int(stack);
1564 node->num_tags = ((tre_union_t *)node->obj)->left->num_tags
1565 + ((tre_union_t *)node->obj)->right->num_tags + added_tags
1566 + ((node->num_submatches > 0) ? 2 : 0);
1568 regset = tre_stack_pop_voidptr(stack);
1569 tag_left = tre_stack_pop_int(stack);
1570 tag_right = tre_stack_pop_int(stack);
1572 /* Add tags after both children, the left child gets a smaller
1573 tag than the right child. This guarantees that we prefer
1574 the left child over the right child. */
1575 /* XXX - This is not always necessary (if the children have
1576 tags which must be seen for every match of that child). */
1577 /* XXX - Check if this is the only place where tre_add_tag_right
1578 is used. If so, use tre_add_tag_left (putting the tag before
1579 the child as opposed after the child) and throw away
1580 tre_add_tag_right. */
1581 if (node->num_submatches > 0)
1585 status = tre_add_tag_right(mem, left, tag_left);
1586 tnfa->tag_directions[tag_left] = TRE_TAG_MAXIMIZE;
1587 if (status == REG_OK)
1588 status = tre_add_tag_right(mem, right, tag_right);
1589 tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE;
1593 direction = TRE_TAG_MAXIMIZE;
1601 } /* end switch(symbol) */
1602 } /* end while(tre_stack_num_objects(stack) > bottom) */
1605 tre_purge_regset(regset, tnfa, tag);
1607 if (!first_pass && minimal_tag >= 0)
1610 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1611 tnfa->minimal_tags[i] = tag;
1612 tnfa->minimal_tags[i + 1] = minimal_tag;
1613 tnfa->minimal_tags[i + 2] = -1;
1618 assert(tree->num_tags == num_tags);
1619 tnfa->end_tag = num_tags;
1620 tnfa->num_tags = num_tags;
1621 tnfa->num_minimals = num_minimals;
1624 xfree(saved_states);
1631 AST to TNFA compilation routines.
1637 } tre_copyast_symbol_t;
1639 /* Flags for tre_copy_ast(). */
1640 #define COPY_REMOVE_TAGS 1
1641 #define COPY_MAXIMIZE_FIRST_TAG 2
1643 static reg_errcode_t
1644 tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
1645 int flags, int *pos_add, tre_tag_direction_t *tag_directions,
1646 tre_ast_node_t **copy, int *max_pos)
1648 reg_errcode_t status = REG_OK;
1649 int bottom = tre_stack_num_objects(stack);
1652 tre_ast_node_t **result = copy;
1653 tre_copyast_symbol_t symbol;
1655 STACK_PUSH(stack, voidptr, ast);
1656 STACK_PUSH(stack, int, COPY_RECURSE);
1658 while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
1660 tre_ast_node_t *node;
1661 if (status != REG_OK)
1664 symbol = (tre_copyast_symbol_t)tre_stack_pop_int(stack);
1667 case COPY_SET_RESULT_PTR:
1668 result = tre_stack_pop_voidptr(stack);
1671 node = tre_stack_pop_voidptr(stack);
1676 tre_literal_t *lit = node->obj;
1677 int pos = lit->position;
1678 int min = lit->code_min;
1679 int max = lit->code_max;
1680 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1682 /* XXX - e.g. [ab] has only one position but two
1683 nodes, so we are creating holes in the state space
1684 here. Not fatal, just wastes memory. */
1688 else if (IS_TAG(lit) && (flags & COPY_REMOVE_TAGS))
1690 /* Change this tag to empty. */
1694 else if (IS_TAG(lit) && (flags & COPY_MAXIMIZE_FIRST_TAG)
1697 /* Maximize the first tag. */
1698 tag_directions[max] = TRE_TAG_MAXIMIZE;
1701 *result = tre_ast_new_literal(mem, min, max, pos);
1702 if (*result == NULL)
1703 status = REG_ESPACE;
1705 tre_literal_t *p = (*result)->obj;
1706 p->class = lit->class;
1707 p->neg_classes = lit->neg_classes;
1716 tre_union_t *uni = node->obj;
1718 *result = tre_ast_new_union(mem, uni->left, uni->right);
1719 if (*result == NULL)
1721 status = REG_ESPACE;
1724 tmp = (*result)->obj;
1725 result = &tmp->left;
1726 STACK_PUSHX(stack, voidptr, uni->right);
1727 STACK_PUSHX(stack, int, COPY_RECURSE);
1728 STACK_PUSHX(stack, voidptr, &tmp->right);
1729 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
1730 STACK_PUSHX(stack, voidptr, uni->left);
1731 STACK_PUSHX(stack, int, COPY_RECURSE);
1736 tre_catenation_t *cat = node->obj;
1737 tre_catenation_t *tmp;
1738 *result = tre_ast_new_catenation(mem, cat->left, cat->right);
1739 if (*result == NULL)
1741 status = REG_ESPACE;
1744 tmp = (*result)->obj;
1747 result = &tmp->left;
1749 STACK_PUSHX(stack, voidptr, cat->right);
1750 STACK_PUSHX(stack, int, COPY_RECURSE);
1751 STACK_PUSHX(stack, voidptr, &tmp->right);
1752 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
1753 STACK_PUSHX(stack, voidptr, cat->left);
1754 STACK_PUSHX(stack, int, COPY_RECURSE);
1759 tre_iteration_t *iter = node->obj;
1760 STACK_PUSHX(stack, voidptr, iter->arg);
1761 STACK_PUSHX(stack, int, COPY_RECURSE);
1762 *result = tre_ast_new_iter(mem, iter->arg, iter->min,
1763 iter->max, iter->minimal);
1764 if (*result == NULL)
1766 status = REG_ESPACE;
1769 iter = (*result)->obj;
1770 result = &iter->arg;
1780 *pos_add += num_copied;
1787 } tre_expand_ast_symbol_t;
1789 /* Expands each iteration node that has a finite nonzero minimum or maximum
1790 iteration count to a catenated sequence of copies of the node. */
1791 static reg_errcode_t
1792 tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
1793 int *position, tre_tag_direction_t *tag_directions)
1795 reg_errcode_t status = REG_OK;
1796 int bottom = tre_stack_num_objects(stack);
1798 int pos_add_total = 0;
1802 STACK_PUSHR(stack, voidptr, ast);
1803 STACK_PUSHR(stack, int, EXPAND_RECURSE);
1804 while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
1806 tre_ast_node_t *node;
1807 tre_expand_ast_symbol_t symbol;
1809 if (status != REG_OK)
1812 symbol = (tre_expand_ast_symbol_t)tre_stack_pop_int(stack);
1813 node = tre_stack_pop_voidptr(stack);
1816 case EXPAND_RECURSE:
1821 tre_literal_t *lit= node->obj;
1822 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1824 lit->position += pos_add;
1825 if (lit->position > max_pos)
1826 max_pos = lit->position;
1832 tre_union_t *uni = node->obj;
1833 STACK_PUSHX(stack, voidptr, uni->right);
1834 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1835 STACK_PUSHX(stack, voidptr, uni->left);
1836 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1841 tre_catenation_t *cat = node->obj;
1842 STACK_PUSHX(stack, voidptr, cat->right);
1843 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1844 STACK_PUSHX(stack, voidptr, cat->left);
1845 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1850 tre_iteration_t *iter = node->obj;
1851 STACK_PUSHX(stack, int, pos_add);
1852 STACK_PUSHX(stack, voidptr, node);
1853 STACK_PUSHX(stack, int, EXPAND_AFTER_ITER);
1854 STACK_PUSHX(stack, voidptr, iter->arg);
1855 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1856 /* If we are going to expand this node at EXPAND_AFTER_ITER
1857 then don't increase the `pos' fields of the nodes now, it
1858 will get done when expanding. */
1859 if (iter->min > 1 || iter->max > 1)
1869 case EXPAND_AFTER_ITER:
1871 tre_iteration_t *iter = node->obj;
1873 pos_add = tre_stack_pop_int(stack);
1874 pos_add_last = pos_add;
1875 if (iter->min > 1 || iter->max > 1)
1877 tre_ast_node_t *seq1 = NULL, *seq2 = NULL;
1879 int pos_add_save = pos_add;
1881 /* Create a catenated sequence of copies of the node. */
1882 for (j = 0; j < iter->min; j++)
1884 tre_ast_node_t *copy;
1885 /* Remove tags from all but the last copy. */
1886 int flags = ((j + 1 < iter->min)
1888 : COPY_MAXIMIZE_FIRST_TAG);
1889 pos_add_save = pos_add;
1890 status = tre_copy_ast(mem, stack, iter->arg, flags,
1891 &pos_add, tag_directions, ©,
1893 if (status != REG_OK)
1896 seq1 = tre_ast_new_catenation(mem, seq1, copy);
1903 if (iter->max == -1)
1905 /* No upper limit. */
1906 pos_add_save = pos_add;
1907 status = tre_copy_ast(mem, stack, iter->arg, 0,
1908 &pos_add, NULL, &seq2, &max_pos);
1909 if (status != REG_OK)
1911 seq2 = tre_ast_new_iter(mem, seq2, 0, -1, 0);
1917 for (j = iter->min; j < iter->max; j++)
1919 tre_ast_node_t *tmp, *copy;
1920 pos_add_save = pos_add;
1921 status = tre_copy_ast(mem, stack, iter->arg, 0,
1922 &pos_add, NULL, ©, &max_pos);
1923 if (status != REG_OK)
1926 seq2 = tre_ast_new_catenation(mem, copy, seq2);
1931 tmp = tre_ast_new_literal(mem, EMPTY, -1, -1);
1934 seq2 = tre_ast_new_union(mem, tmp, seq2);
1940 pos_add = pos_add_save;
1943 else if (seq2 != NULL)
1944 seq1 = tre_ast_new_catenation(mem, seq1, seq2);
1947 node->obj = seq1->obj;
1948 node->type = seq1->type;
1952 pos_add_total += pos_add - pos_add_last;
1953 if (iter_depth == 0)
1954 pos_add = pos_add_total;
1964 *position += pos_add_total;
1966 /* `max_pos' should never be larger than `*position' if the above
1967 code works, but just an extra safeguard let's make sure
1968 `*position' is set large enough so enough memory will be
1969 allocated for the transition table. */
1970 if (max_pos > *position)
1971 *position = max_pos;
1976 static tre_pos_and_tags_t *
1977 tre_set_empty(tre_mem_t mem)
1979 tre_pos_and_tags_t *new_set;
1981 new_set = tre_mem_calloc(mem, sizeof(*new_set));
1982 if (new_set == NULL)
1985 new_set[0].position = -1;
1986 new_set[0].code_min = -1;
1987 new_set[0].code_max = -1;
1992 static tre_pos_and_tags_t *
1993 tre_set_one(tre_mem_t mem, int position, int code_min, int code_max,
1994 tre_ctype_t class, tre_ctype_t *neg_classes, int backref)
1996 tre_pos_and_tags_t *new_set;
1998 new_set = tre_mem_calloc(mem, sizeof(*new_set) * 2);
1999 if (new_set == NULL)
2002 new_set[0].position = position;
2003 new_set[0].code_min = code_min;
2004 new_set[0].code_max = code_max;
2005 new_set[0].class = class;
2006 new_set[0].neg_classes = neg_classes;
2007 new_set[0].backref = backref;
2008 new_set[1].position = -1;
2009 new_set[1].code_min = -1;
2010 new_set[1].code_max = -1;
2015 static tre_pos_and_tags_t *
2016 tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2,
2017 int *tags, int assertions)
2020 tre_pos_and_tags_t *new_set;
2024 for (num_tags = 0; tags != NULL && tags[num_tags] >= 0; num_tags++);
2025 for (s1 = 0; set1[s1].position >= 0; s1++);
2026 for (s2 = 0; set2[s2].position >= 0; s2++);
2027 new_set = tre_mem_calloc(mem, sizeof(*new_set) * (s1 + s2 + 1));
2031 for (s1 = 0; set1[s1].position >= 0; s1++)
2033 new_set[s1].position = set1[s1].position;
2034 new_set[s1].code_min = set1[s1].code_min;
2035 new_set[s1].code_max = set1[s1].code_max;
2036 new_set[s1].assertions = set1[s1].assertions | assertions;
2037 new_set[s1].class = set1[s1].class;
2038 new_set[s1].neg_classes = set1[s1].neg_classes;
2039 new_set[s1].backref = set1[s1].backref;
2040 if (set1[s1].tags == NULL && tags == NULL)
2041 new_set[s1].tags = NULL;
2044 for (i = 0; set1[s1].tags != NULL && set1[s1].tags[i] >= 0; i++);
2045 new_tags = tre_mem_alloc(mem, (sizeof(*new_tags)
2046 * (i + num_tags + 1)));
2047 if (new_tags == NULL)
2049 for (j = 0; j < i; j++)
2050 new_tags[j] = set1[s1].tags[j];
2051 for (i = 0; i < num_tags; i++)
2052 new_tags[j + i] = tags[i];
2053 new_tags[j + i] = -1;
2054 new_set[s1].tags = new_tags;
2058 for (s2 = 0; set2[s2].position >= 0; s2++)
2060 new_set[s1 + s2].position = set2[s2].position;
2061 new_set[s1 + s2].code_min = set2[s2].code_min;
2062 new_set[s1 + s2].code_max = set2[s2].code_max;
2063 /* XXX - why not | assertions here as well? */
2064 new_set[s1 + s2].assertions = set2[s2].assertions;
2065 new_set[s1 + s2].class = set2[s2].class;
2066 new_set[s1 + s2].neg_classes = set2[s2].neg_classes;
2067 new_set[s1 + s2].backref = set2[s2].backref;
2068 if (set2[s2].tags == NULL)
2069 new_set[s1 + s2].tags = NULL;
2072 for (i = 0; set2[s2].tags[i] >= 0; i++);
2073 new_tags = tre_mem_alloc(mem, sizeof(*new_tags) * (i + 1));
2074 if (new_tags == NULL)
2076 for (j = 0; j < i; j++)
2077 new_tags[j] = set2[s2].tags[j];
2079 new_set[s1 + s2].tags = new_tags;
2082 new_set[s1 + s2].position = -1;
2086 /* Finds the empty path through `node' which is the one that should be
2087 taken according to POSIX.2 rules, and adds the tags on that path to
2088 `tags'. `tags' may be NULL. If `num_tags_seen' is not NULL, it is
2089 set to the number of tags seen on the path. */
2090 static reg_errcode_t
2091 tre_match_empty(tre_stack_t *stack, tre_ast_node_t *node, int *tags,
2092 int *assertions, int *num_tags_seen)
2096 tre_catenation_t *cat;
2097 tre_iteration_t *iter;
2099 int bottom = tre_stack_num_objects(stack);
2100 reg_errcode_t status = REG_OK;
2104 status = tre_stack_push_voidptr(stack, node);
2106 /* Walk through the tree recursively. */
2107 while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2109 node = tre_stack_pop_voidptr(stack);
2114 lit = (tre_literal_t *)node->obj;
2115 switch (lit->code_min)
2118 if (lit->code_max >= 0)
2122 /* Add the tag to `tags'. */
2123 for (i = 0; tags[i] >= 0; i++)
2124 if (tags[i] == lit->code_max)
2128 tags[i] = lit->code_max;
2137 assert(lit->code_max >= 1
2138 || lit->code_max <= ASSERT_LAST);
2139 if (assertions != NULL)
2140 *assertions |= lit->code_max;
2151 /* Subexpressions starting earlier take priority over ones
2152 starting later, so we prefer the left subexpression over the
2153 right subexpression. */
2154 uni = (tre_union_t *)node->obj;
2155 if (uni->left->nullable)
2156 STACK_PUSHX(stack, voidptr, uni->left)
2157 else if (uni->right->nullable)
2158 STACK_PUSHX(stack, voidptr, uni->right)
2164 /* The path must go through both children. */
2165 cat = (tre_catenation_t *)node->obj;
2166 assert(cat->left->nullable);
2167 assert(cat->right->nullable);
2168 STACK_PUSHX(stack, voidptr, cat->left);
2169 STACK_PUSHX(stack, voidptr, cat->right);
2173 /* A match with an empty string is preferred over no match at
2174 all, so we go through the argument if possible. */
2175 iter = (tre_iteration_t *)node->obj;
2176 if (iter->arg->nullable)
2177 STACK_PUSHX(stack, voidptr, iter->arg);
2193 NFL_POST_CATENATION,
2195 } tre_nfl_stack_symbol_t;
2198 /* Computes and fills in the fields `nullable', `firstpos', and `lastpos' for
2199 the nodes of the AST `tree'. */
2200 static reg_errcode_t
2201 tre_compute_nfl(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree)
2203 int bottom = tre_stack_num_objects(stack);
2205 STACK_PUSHR(stack, voidptr, tree);
2206 STACK_PUSHR(stack, int, NFL_RECURSE);
2208 while (tre_stack_num_objects(stack) > bottom)
2210 tre_nfl_stack_symbol_t symbol;
2211 tre_ast_node_t *node;
2213 symbol = (tre_nfl_stack_symbol_t)tre_stack_pop_int(stack);
2214 node = tre_stack_pop_voidptr(stack);
2222 tre_literal_t *lit = (tre_literal_t *)node->obj;
2223 if (IS_BACKREF(lit))
2225 /* Back references: nullable = false, firstpos = {i},
2228 node->firstpos = tre_set_one(mem, lit->position, 0,
2229 TRE_CHAR_MAX, 0, NULL, -1);
2230 if (!node->firstpos)
2232 node->lastpos = tre_set_one(mem, lit->position, 0,
2233 TRE_CHAR_MAX, 0, NULL,
2234 (int)lit->code_max);
2238 else if (lit->code_min < 0)
2240 /* Tags, empty strings, params, and zero width assertions:
2241 nullable = true, firstpos = {}, and lastpos = {}. */
2243 node->firstpos = tre_set_empty(mem);
2244 if (!node->firstpos)
2246 node->lastpos = tre_set_empty(mem);
2252 /* Literal at position i: nullable = false, firstpos = {i},
2256 tre_set_one(mem, lit->position, (int)lit->code_min,
2257 (int)lit->code_max, 0, NULL, -1);
2258 if (!node->firstpos)
2260 node->lastpos = tre_set_one(mem, lit->position,
2263 lit->class, lit->neg_classes,
2272 /* Compute the attributes for the two subtrees, and after that
2274 STACK_PUSHR(stack, voidptr, node);
2275 STACK_PUSHR(stack, int, NFL_POST_UNION);
2276 STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->right);
2277 STACK_PUSHR(stack, int, NFL_RECURSE);
2278 STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->left);
2279 STACK_PUSHR(stack, int, NFL_RECURSE);
2283 /* Compute the attributes for the two subtrees, and after that
2285 STACK_PUSHR(stack, voidptr, node);
2286 STACK_PUSHR(stack, int, NFL_POST_CATENATION);
2287 STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->right);
2288 STACK_PUSHR(stack, int, NFL_RECURSE);
2289 STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->left);
2290 STACK_PUSHR(stack, int, NFL_RECURSE);
2294 /* Compute the attributes for the subtree, and after that for
2296 STACK_PUSHR(stack, voidptr, node);
2297 STACK_PUSHR(stack, int, NFL_POST_ITERATION);
2298 STACK_PUSHR(stack, voidptr, ((tre_iteration_t *)node->obj)->arg);
2299 STACK_PUSHR(stack, int, NFL_RECURSE);
2302 break; /* end case: NFL_RECURSE */
2304 case NFL_POST_UNION:
2306 tre_union_t *uni = (tre_union_t *)node->obj;
2307 node->nullable = uni->left->nullable || uni->right->nullable;
2308 node->firstpos = tre_set_union(mem, uni->left->firstpos,
2309 uni->right->firstpos, NULL, 0);
2310 if (!node->firstpos)
2312 node->lastpos = tre_set_union(mem, uni->left->lastpos,
2313 uni->right->lastpos, NULL, 0);
2319 case NFL_POST_ITERATION:
2321 tre_iteration_t *iter = (tre_iteration_t *)node->obj;
2323 if (iter->min == 0 || iter->arg->nullable)
2327 node->firstpos = iter->arg->firstpos;
2328 node->lastpos = iter->arg->lastpos;
2332 case NFL_POST_CATENATION:
2334 int num_tags, *tags, assertions;
2335 reg_errcode_t status;
2336 tre_catenation_t *cat = node->obj;
2337 node->nullable = cat->left->nullable && cat->right->nullable;
2339 /* Compute firstpos. */
2340 if (cat->left->nullable)
2342 /* The left side matches the empty string. Make a first pass
2343 with tre_match_empty() to get the number of tags and
2345 status = tre_match_empty(stack, cat->left,
2346 NULL, NULL, &num_tags);
2347 if (status != REG_OK)
2349 /* Allocate arrays for the tags and parameters. */
2350 tags = xmalloc(sizeof(*tags) * (num_tags + 1));
2355 /* Second pass with tre_mach_empty() to get the list of
2356 tags and parameters. */
2357 status = tre_match_empty(stack, cat->left, tags,
2359 if (status != REG_OK)
2365 tre_set_union(mem, cat->right->firstpos, cat->left->firstpos,
2368 if (!node->firstpos)
2373 node->firstpos = cat->left->firstpos;
2376 /* Compute lastpos. */
2377 if (cat->right->nullable)
2379 /* The right side matches the empty string. Make a first pass
2380 with tre_match_empty() to get the number of tags and
2382 status = tre_match_empty(stack, cat->right,
2383 NULL, NULL, &num_tags);
2384 if (status != REG_OK)
2386 /* Allocate arrays for the tags and parameters. */
2387 tags = xmalloc(sizeof(int) * (num_tags + 1));
2392 /* Second pass with tre_mach_empty() to get the list of
2393 tags and parameters. */
2394 status = tre_match_empty(stack, cat->right, tags,
2396 if (status != REG_OK)
2402 tre_set_union(mem, cat->left->lastpos, cat->right->lastpos,
2410 node->lastpos = cat->right->lastpos;
2425 /* Adds a transition from each position in `p1' to each position in `p2'. */
2426 static reg_errcode_t
2427 tre_make_trans(tre_pos_and_tags_t *p1, tre_pos_and_tags_t *p2,
2428 tre_tnfa_transition_t *transitions,
2429 int *counts, int *offs)
2431 tre_pos_and_tags_t *orig_p2 = p2;
2432 tre_tnfa_transition_t *trans;
2433 int i, j, k, l, dup, prev_p2_pos;
2435 if (transitions != NULL)
2436 while (p1->position >= 0)
2440 while (p2->position >= 0)
2442 /* Optimization: if this position was already handled, skip it. */
2443 if (p2->position == prev_p2_pos)
2448 prev_p2_pos = p2->position;
2449 /* Set `trans' to point to the next unused transition from
2450 position `p1->position'. */
2451 trans = transitions + offs[p1->position];
2452 while (trans->state != NULL)
2455 /* If we find a previous transition from `p1->position' to
2456 `p2->position', it is overwritten. This can happen only
2457 if there are nested loops in the regexp, like in "((a)*)*".
2458 In POSIX.2 repetition using the outer loop is always
2459 preferred over using the inner loop. Therefore the
2460 transition for the inner loop is useless and can be thrown
2462 /* XXX - The same position is used for all nodes in a bracket
2463 expression, so this optimization cannot be used (it will
2464 break bracket expressions) unless I figure out a way to
2466 if (trans->state_id == p2->position)
2474 if (trans->state == NULL)
2475 (trans + 1)->state = NULL;
2476 /* Use the character ranges, assertions, etc. from `p1' for
2477 the transition from `p1' to `p2'. */
2478 trans->code_min = p1->code_min;
2479 trans->code_max = p1->code_max;
2480 trans->state = transitions + offs[p2->position];
2481 trans->state_id = p2->position;
2482 trans->assertions = p1->assertions | p2->assertions
2483 | (p1->class ? ASSERT_CHAR_CLASS : 0)
2484 | (p1->neg_classes != NULL ? ASSERT_CHAR_CLASS_NEG : 0);
2485 if (p1->backref >= 0)
2487 assert((trans->assertions & ASSERT_CHAR_CLASS) == 0);
2488 assert(p2->backref < 0);
2489 trans->u.backref = p1->backref;
2490 trans->assertions |= ASSERT_BACKREF;
2493 trans->u.class = p1->class;
2494 if (p1->neg_classes != NULL)
2496 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++);
2497 trans->neg_classes =
2498 xmalloc(sizeof(*trans->neg_classes) * (i + 1));
2499 if (trans->neg_classes == NULL)
2501 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++)
2502 trans->neg_classes[i] = p1->neg_classes[i];
2503 trans->neg_classes[i] = (tre_ctype_t)0;
2506 trans->neg_classes = NULL;
2508 /* Find out how many tags this transition has. */
2510 if (p1->tags != NULL)
2511 while(p1->tags[i] >= 0)
2514 if (p2->tags != NULL)
2515 while(p2->tags[j] >= 0)
2518 /* If we are overwriting a transition, free the old tag array. */
2519 if (trans->tags != NULL)
2523 /* If there were any tags, allocate an array and fill it. */
2526 trans->tags = xmalloc(sizeof(*trans->tags) * (i + j + 1));
2530 if (p1->tags != NULL)
2531 while(p1->tags[i] >= 0)
2533 trans->tags[i] = p1->tags[i];
2538 if (p2->tags != NULL)
2539 while (p2->tags[j] >= 0)
2541 /* Don't add duplicates. */
2543 for (k = 0; k < i; k++)
2544 if (trans->tags[k] == p2->tags[j])
2550 trans->tags[l++] = p2->tags[j];
2553 trans->tags[l] = -1;
2561 /* Compute a maximum limit for the number of transitions leaving
2563 while (p1->position >= 0)
2566 while (p2->position >= 0)
2568 counts[p1->position]++;
2576 /* Converts the syntax tree to a TNFA. All the transitions in the TNFA are
2577 labelled with one character range (there are no transitions on empty
2578 strings). The TNFA takes O(n^2) space in the worst case, `n' is size of
2580 static reg_errcode_t
2581 tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions,
2582 int *counts, int *offs)
2585 tre_catenation_t *cat;
2586 tre_iteration_t *iter;
2587 reg_errcode_t errcode = REG_OK;
2589 /* XXX - recurse using a stack!. */
2595 uni = (tre_union_t *)node->obj;
2596 errcode = tre_ast_to_tnfa(uni->left, transitions, counts, offs);
2597 if (errcode != REG_OK)
2599 errcode = tre_ast_to_tnfa(uni->right, transitions, counts, offs);
2603 cat = (tre_catenation_t *)node->obj;
2604 /* Add a transition from each position in cat->left->lastpos
2605 to each position in cat->right->firstpos. */
2606 errcode = tre_make_trans(cat->left->lastpos, cat->right->firstpos,
2607 transitions, counts, offs);
2608 if (errcode != REG_OK)
2610 errcode = tre_ast_to_tnfa(cat->left, transitions, counts, offs);
2611 if (errcode != REG_OK)
2613 errcode = tre_ast_to_tnfa(cat->right, transitions, counts, offs);
2617 iter = (tre_iteration_t *)node->obj;
2618 assert(iter->max == -1 || iter->max == 1);
2620 if (iter->max == -1)
2622 assert(iter->min == 0 || iter->min == 1);
2623 /* Add a transition from each last position in the iterated
2624 expression to each first position. */
2625 errcode = tre_make_trans(iter->arg->lastpos, iter->arg->firstpos,
2626 transitions, counts, offs);
2627 if (errcode != REG_OK)
2630 errcode = tre_ast_to_tnfa(iter->arg, transitions, counts, offs);
2637 #define ERROR_EXIT(err) \
2641 if (/*CONSTCOND*/1) \
2644 while (/*CONSTCOND*/0)
2648 regcomp(regex_t *restrict preg, const char *restrict regex, int cflags)
2651 tre_ast_node_t *tree, *tmp_ast_l, *tmp_ast_r;
2652 tre_pos_and_tags_t *p;
2653 int *counts = NULL, *offs = NULL;
2655 tre_tnfa_transition_t *transitions, *initial;
2656 tre_tnfa_t *tnfa = NULL;
2657 tre_submatch_data_t *submatch_data;
2658 tre_tag_direction_t *tag_directions = NULL;
2659 reg_errcode_t errcode;
2662 /* Parse context. */
2663 tre_parse_ctx_t parse_ctx;
2665 /* Allocate a stack used throughout the compilation process for various
2667 stack = tre_stack_new(512, 10240, 128);
2670 /* Allocate a fast memory allocator. */
2671 mem = tre_mem_new();
2674 tre_stack_destroy(stack);
2678 /* Parse the regexp. */
2679 memset(&parse_ctx, 0, sizeof(parse_ctx));
2680 parse_ctx.mem = mem;
2681 parse_ctx.stack = stack;
2682 parse_ctx.re = regex;
2683 parse_ctx.cflags = cflags;
2684 parse_ctx.max_backref = -1;
2685 errcode = tre_parse(&parse_ctx);
2686 if (errcode != REG_OK)
2687 ERROR_EXIT(errcode);
2688 preg->re_nsub = parse_ctx.submatch_id - 1;
2692 tre_ast_print(tree);
2693 #endif /* TRE_DEBUG */
2695 /* Referring to nonexistent subexpressions is illegal. */
2696 if (parse_ctx.max_backref > (int)preg->re_nsub)
2697 ERROR_EXIT(REG_ESUBREG);
2699 /* Allocate the TNFA struct. */
2700 tnfa = xcalloc(1, sizeof(tre_tnfa_t));
2702 ERROR_EXIT(REG_ESPACE);
2703 tnfa->have_backrefs = parse_ctx.max_backref >= 0;
2704 tnfa->have_approx = 0;
2705 tnfa->num_submatches = parse_ctx.submatch_id;
2707 /* Set up tags for submatch addressing. If REG_NOSUB is set and the
2708 regexp does not have back references, this can be skipped. */
2709 if (tnfa->have_backrefs || !(cflags & REG_NOSUB))
2712 /* Figure out how many tags we will need. */
2713 errcode = tre_add_tags(NULL, stack, tree, tnfa);
2714 if (errcode != REG_OK)
2715 ERROR_EXIT(errcode);
2717 if (tnfa->num_tags > 0)
2719 tag_directions = xmalloc(sizeof(*tag_directions)
2720 * (tnfa->num_tags + 1));
2721 if (tag_directions == NULL)
2722 ERROR_EXIT(REG_ESPACE);
2723 tnfa->tag_directions = tag_directions;
2724 memset(tag_directions, -1,
2725 sizeof(*tag_directions) * (tnfa->num_tags + 1));
2727 tnfa->minimal_tags = xcalloc((unsigned)tnfa->num_tags * 2 + 1,
2728 sizeof(*tnfa->minimal_tags));
2729 if (tnfa->minimal_tags == NULL)
2730 ERROR_EXIT(REG_ESPACE);
2732 submatch_data = xcalloc((unsigned)parse_ctx.submatch_id,
2733 sizeof(*submatch_data));
2734 if (submatch_data == NULL)
2735 ERROR_EXIT(REG_ESPACE);
2736 tnfa->submatch_data = submatch_data;
2738 errcode = tre_add_tags(mem, stack, tree, tnfa);
2739 if (errcode != REG_OK)
2740 ERROR_EXIT(errcode);
2744 /* Expand iteration nodes. */
2745 errcode = tre_expand_ast(mem, stack, tree, &parse_ctx.position,
2747 if (errcode != REG_OK)
2748 ERROR_EXIT(errcode);
2750 /* Add a dummy node for the final state.
2751 XXX - For certain patterns this dummy node can be optimized away,
2752 for example "a*" or "ab*". Figure out a simple way to detect
2753 this possibility. */
2755 tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position++);
2756 if (tmp_ast_r == NULL)
2757 ERROR_EXIT(REG_ESPACE);
2759 tree = tre_ast_new_catenation(mem, tmp_ast_l, tmp_ast_r);
2761 ERROR_EXIT(REG_ESPACE);
2763 errcode = tre_compute_nfl(mem, stack, tree);
2764 if (errcode != REG_OK)
2765 ERROR_EXIT(errcode);
2767 counts = xmalloc(sizeof(int) * parse_ctx.position);
2769 ERROR_EXIT(REG_ESPACE);
2771 offs = xmalloc(sizeof(int) * parse_ctx.position);
2773 ERROR_EXIT(REG_ESPACE);
2775 for (i = 0; i < parse_ctx.position; i++)
2777 tre_ast_to_tnfa(tree, NULL, counts, NULL);
2780 for (i = 0; i < parse_ctx.position; i++)
2783 add += counts[i] + 1;
2786 transitions = xcalloc((unsigned)add + 1, sizeof(*transitions));
2787 if (transitions == NULL)
2788 ERROR_EXIT(REG_ESPACE);
2789 tnfa->transitions = transitions;
2790 tnfa->num_transitions = add;
2792 errcode = tre_ast_to_tnfa(tree, transitions, counts, offs);
2793 if (errcode != REG_OK)
2794 ERROR_EXIT(errcode);
2796 tnfa->firstpos_chars = NULL;
2800 while (p->position >= 0)
2806 initial = xcalloc((unsigned)i + 1, sizeof(tre_tnfa_transition_t));
2807 if (initial == NULL)
2808 ERROR_EXIT(REG_ESPACE);
2809 tnfa->initial = initial;
2812 for (p = tree->firstpos; p->position >= 0; p++)
2814 initial[i].state = transitions + offs[p->position];
2815 initial[i].state_id = p->position;
2816 initial[i].tags = NULL;
2817 /* Copy the arrays p->tags, and p->params, they are allocated
2818 from a tre_mem object. */
2822 for (j = 0; p->tags[j] >= 0; j++);
2823 initial[i].tags = xmalloc(sizeof(*p->tags) * (j + 1));
2824 if (!initial[i].tags)
2825 ERROR_EXIT(REG_ESPACE);
2826 memcpy(initial[i].tags, p->tags, sizeof(*p->tags) * (j + 1));
2828 initial[i].assertions = p->assertions;
2831 initial[i].state = NULL;
2833 tnfa->num_transitions = add;
2834 tnfa->final = transitions + offs[tree->lastpos[0].position];
2835 tnfa->num_states = parse_ctx.position;
2836 tnfa->cflags = cflags;
2838 tre_mem_destroy(mem);
2839 tre_stack_destroy(stack);
2843 preg->TRE_REGEX_T_FIELD = (void *)tnfa;
2847 /* Free everything that was allocated and return the error code. */
2848 tre_mem_destroy(mem);
2850 tre_stack_destroy(stack);
2855 preg->TRE_REGEX_T_FIELD = (void *)tnfa;
2864 regfree(regex_t *preg)
2868 tre_tnfa_transition_t *trans;
2870 tnfa = (void *)preg->TRE_REGEX_T_FIELD;
2874 for (i = 0; i < tnfa->num_transitions; i++)
2875 if (tnfa->transitions[i].state)
2877 if (tnfa->transitions[i].tags)
2878 xfree(tnfa->transitions[i].tags);
2879 if (tnfa->transitions[i].neg_classes)
2880 xfree(tnfa->transitions[i].neg_classes);
2882 if (tnfa->transitions)
2883 xfree(tnfa->transitions);
2887 for (trans = tnfa->initial; trans->state; trans++)
2892 xfree(tnfa->initial);
2895 if (tnfa->submatch_data)
2897 for (i = 0; i < tnfa->num_submatches; i++)
2898 if (tnfa->submatch_data[i].parents)
2899 xfree(tnfa->submatch_data[i].parents);
2900 xfree(tnfa->submatch_data);
2903 if (tnfa->tag_directions)
2904 xfree(tnfa->tag_directions);
2905 if (tnfa->firstpos_chars)
2906 xfree(tnfa->firstpos_chars);
2907 if (tnfa->minimal_tags)
2908 xfree(tnfa->minimal_tags);