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 last subexpression parsed. */
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;
640 * With REG_NEWLINE, POSIX requires that newlines are not matched by
641 * any form of a non-matching list.
643 if (ctx->cflags & REG_NEWLINE) {
644 lit = tre_new_lit(&ls);
647 goto parse_bracket_done;
649 lit->code_min = '\n';
650 lit->code_max = '\n';
653 /* Sort the array if we need to negate it. */
654 qsort(ls.a, ls.len, sizeof *ls.a, tre_compare_lit);
655 /* extra lit for the last negated range */
656 lit = tre_new_lit(&ls);
659 goto parse_bracket_done;
661 lit->code_min = TRE_CHAR_MAX+1;
662 lit->code_max = TRE_CHAR_MAX+1;
664 /* negated classes */
666 nc = tre_mem_alloc(ctx->mem, (neg.len+1)*sizeof *neg.a);
669 goto parse_bracket_done;
671 memcpy(nc, neg.a, neg.len*sizeof *neg.a);
676 /* Build a union of the items in the array, negated if necessary. */
678 for (i = 0; i < ls.len; i++) {
685 negmin = MAX(max + 1, negmin);
689 lit->code_min = negmin;
690 lit->code_max = negmax;
693 lit->position = ctx->position;
694 lit->neg_classes = nc;
695 n = tre_ast_new_node(ctx->mem, LITERAL, lit);
696 node = tre_ast_new_union(ctx->mem, node, n);
710 static const char *parse_dup_count(const char *s, int *n)
717 *n = 10 * *n + (*s - '0');
719 if (!isdigit(*s) || *n > RE_DUP_MAX)
725 static const char *parse_dup(const char *s, int ere, int *pmin, int *pmax)
729 s = parse_dup_count(s, &min);
731 s = parse_dup_count(s+1, &max);
736 (max < min && max >= 0) ||
740 (!ere && *s++ != '\\') ||
749 static int hexval(unsigned c)
751 if (c-'0'<10) return c-'0';
753 if (c-'a'<6) return c-'a'+10;
757 static reg_errcode_t marksub(tre_parse_ctx_t *ctx, tre_ast_node_t *node, int subid)
759 if (node->submatch_id >= 0) {
760 tre_ast_node_t *n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
763 n = tre_ast_new_catenation(ctx->mem, n, node);
766 n->num_submatches = node->num_submatches;
769 node->submatch_id = subid;
770 node->num_submatches++;
777 Regex = Branch | '^' | '$' | '^$' | '^' Branch | Branch '$' | '^' Branch '$'
778 Branch = Atom | Branch Atom
779 Atom = char | quoted_char | '.' | Bracket | Atom Dup | '\(' Branch '\)' | back_ref
780 Dup = '*' | '\{' Count '\}' | '\{' Count ',\}' | '\{' Count ',' Count '\}'
782 (leading ^ and trailing $ in a sub expr may be an anchor or literal as well)
785 Regex = Branch | Regex '|' Branch
786 Branch = Atom | Branch Atom
787 Atom = char | quoted_char | '.' | Bracket | Atom Dup | '(' Regex ')' | '^' | '$'
788 Dup = '*' | '+' | '?' | '{' Count '}' | '{' Count ',}' | '{' Count ',' Count '}'
790 (a*+?, ^*, $+, \X, {, (|a) are unspecified)
793 static reg_errcode_t parse_atom(tre_parse_ctx_t *ctx, const char *s)
795 int len, ere = ctx->cflags & REG_EXTENDED;
797 tre_ast_node_t *node;
801 return parse_bracket(ctx, s+1);
803 p = tre_expand_macro(s+1);
805 /* assume \X expansion is a single atom */
806 reg_errcode_t err = parse_atom(ctx, p);
810 /* extensions: \b, \B, \<, \>, \xHH \x{HHHH} */
815 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_WB, -1);
818 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_WB_NEG, -1);
821 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_BOW, -1);
824 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_EOW, -1);
834 for (i=0; i<len && v<0x110000; i++) {
845 node = tre_ast_new_literal(ctx->mem, v, v, ctx->position++);
851 /* extension: treat \+, \? as repetitions in BRE */
852 /* reject repetitions after empty expression in BRE */
856 /* extension: treat \| as alternation in BRE */
858 node = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
864 if (!ere && (unsigned)*s-'1' < 9) {
867 node = tre_ast_new_literal(ctx->mem, BACKREF, val, ctx->position++);
868 ctx->max_backref = MAX(val, ctx->max_backref);
870 /* extension: accept unknown escaped char
878 if (ctx->cflags & REG_NEWLINE) {
879 tre_ast_node_t *tmp1, *tmp2;
880 tmp1 = tre_ast_new_literal(ctx->mem, 0, '\n'-1, ctx->position++);
881 tmp2 = tre_ast_new_literal(ctx->mem, '\n'+1, TRE_CHAR_MAX, ctx->position++);
883 node = tre_ast_new_union(ctx->mem, tmp1, tmp2);
887 node = tre_ast_new_literal(ctx->mem, 0, TRE_CHAR_MAX, ctx->position++);
892 /* '^' has a special meaning everywhere in EREs, and at beginning of BRE. */
893 if (!ere && s != ctx->start)
895 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_BOL, -1);
899 /* '$' is special everywhere in EREs, and at the end of a BRE subexpression. */
900 if (!ere && s[1] && (s[1]!='\\'|| (s[2]!=')' && s[2]!='|')))
902 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_EOL, -1);
909 /* reject repetitions after empty expression in ERE */
916 node = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
920 len = mbtowc(&wc, s, -1);
923 if (ctx->cflags & REG_ICASE && (tre_isupper(wc) || tre_islower(wc))) {
924 tre_ast_node_t *tmp1, *tmp2;
925 /* multiple opposite case characters are not supported */
926 tmp1 = tre_ast_new_literal(ctx->mem, tre_toupper(wc), tre_toupper(wc), ctx->position);
927 tmp2 = tre_ast_new_literal(ctx->mem, tre_tolower(wc), tre_tolower(wc), ctx->position);
929 node = tre_ast_new_union(ctx->mem, tmp1, tmp2);
933 node = tre_ast_new_literal(ctx->mem, wc, wc, ctx->position);
947 #define PUSHPTR(err, s, v) do { \
948 if ((err = tre_stack_push_voidptr(s, v)) != REG_OK) \
952 #define PUSHINT(err, s, v) do { \
953 if ((err = tre_stack_push_int(s, v)) != REG_OK) \
957 static reg_errcode_t tre_parse(tre_parse_ctx_t *ctx)
959 tre_ast_node_t *nbranch=0, *nunion=0;
960 int ere = ctx->cflags & REG_EXTENDED;
961 const char *s = ctx->start;
965 tre_stack_t *stack = ctx->stack;
967 PUSHINT(err, stack, subid++);
969 if ((!ere && *s == '\\' && s[1] == '(') ||
970 (ere && *s == '(')) {
971 PUSHPTR(err, stack, nunion);
972 PUSHPTR(err, stack, nbranch);
973 PUSHINT(err, stack, subid++);
978 nbranch = nunion = 0;
982 if ((!ere && *s == '\\' && s[1] == ')') ||
983 (ere && *s == ')' && depth)) {
984 ctx->n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
988 err = parse_atom(ctx, s);
998 if (*s!='\\' && *s!='*') {
1001 if (*s!='+' && *s!='?' && *s!='{')
1004 if (*s=='\\' && ere)
1006 /* extension: treat \+, \? as repetitions in BRE */
1007 if (*s=='\\' && s[1]!='+' && s[1]!='?' && s[1]!='{')
1012 /* handle ^* at the start of a BRE. */
1013 if (!ere && s==ctx->start+1 && s[-1]=='^')
1016 /* extension: multiple consecutive *+?{,} is unspecified,
1017 but (a+)+ has to be supported so accepting a++ makes
1018 sense, note however that the RE_DUP_MAX limit can be
1019 circumvented: (a{255}){255} uses a lot of memory.. */
1021 s = parse_dup(s+1, ere, &min, &max);
1034 ctx->n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
1036 ctx->n = tre_ast_new_iter(ctx->mem, ctx->n, min, max, 0);
1041 nbranch = tre_ast_new_catenation(ctx->mem, nbranch, ctx->n);
1042 if ((ere && *s == '|') ||
1043 (ere && *s == ')' && depth) ||
1044 (!ere && *s == '\\' && s[1] == ')') ||
1045 /* extension: treat \| as alternation in BRE */
1046 (!ere && *s == '\\' && s[1] == '|') ||
1048 /* extension: empty branch is unspecified (), (|a), (a|)
1049 here they are not rejected but match on empty string */
1051 nunion = tre_ast_new_union(ctx->mem, nunion, nbranch);
1054 if (c == '\\' && s[1] == '|') {
1057 } else if (c == '|') {
1062 if (!depth) return REG_EPAREN;
1064 } else if (c == ')')
1067 err = marksub(ctx, nunion, tre_stack_pop_int(stack));
1070 if (!c && depth<0) {
1071 ctx->submatch_id = subid;
1076 nbranch = tre_stack_pop_voidptr(stack);
1077 nunion = tre_stack_pop_voidptr(stack);
1085 /***********************************************************************
1087 ***********************************************************************/
1092 - Fix tre_ast_to_tnfa() to recurse using a stack instead of recursive
1097 Algorithms to setup tags so that submatch addressing can be done.
1101 /* Inserts a catenation node to the root of the tree given in `node'.
1102 As the left child a new tag with number `tag_id' to `node' is added,
1103 and the right child is the old root. */
1104 static reg_errcode_t
1105 tre_add_tag_left(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1107 tre_catenation_t *c;
1109 c = tre_mem_alloc(mem, sizeof(*c));
1112 c->left = tre_ast_new_literal(mem, TAG, tag_id, -1);
1113 if (c->left == NULL)
1115 c->right = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1116 if (c->right == NULL)
1119 c->right->obj = node->obj;
1120 c->right->type = node->type;
1121 c->right->nullable = -1;
1122 c->right->submatch_id = -1;
1123 c->right->firstpos = NULL;
1124 c->right->lastpos = NULL;
1125 c->right->num_tags = 0;
1126 c->right->num_submatches = 0;
1128 node->type = CATENATION;
1132 /* Inserts a catenation node to the root of the tree given in `node'.
1133 As the right child a new tag with number `tag_id' to `node' is added,
1134 and the left child is the old root. */
1135 static reg_errcode_t
1136 tre_add_tag_right(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1138 tre_catenation_t *c;
1140 c = tre_mem_alloc(mem, sizeof(*c));
1143 c->right = tre_ast_new_literal(mem, TAG, tag_id, -1);
1144 if (c->right == NULL)
1146 c->left = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1147 if (c->left == NULL)
1150 c->left->obj = node->obj;
1151 c->left->type = node->type;
1152 c->left->nullable = -1;
1153 c->left->submatch_id = -1;
1154 c->left->firstpos = NULL;
1155 c->left->lastpos = NULL;
1156 c->left->num_tags = 0;
1157 c->left->num_submatches = 0;
1159 node->type = CATENATION;
1165 ADDTAGS_AFTER_ITERATION,
1166 ADDTAGS_AFTER_UNION_LEFT,
1167 ADDTAGS_AFTER_UNION_RIGHT,
1168 ADDTAGS_AFTER_CAT_LEFT,
1169 ADDTAGS_AFTER_CAT_RIGHT,
1170 ADDTAGS_SET_SUBMATCH_END
1171 } tre_addtags_symbol_t;
1180 /* Go through `regset' and set submatch data for submatches that are
1183 tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag)
1187 for (i = 0; regset[i] >= 0; i++)
1189 int id = regset[i] / 2;
1190 int start = !(regset[i] % 2);
1192 tnfa->submatch_data[id].so_tag = tag;
1194 tnfa->submatch_data[id].eo_tag = tag;
1200 /* Adds tags to appropriate locations in the parse tree in `tree', so that
1201 subexpressions marked for submatch addressing can be traced. */
1202 static reg_errcode_t
1203 tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree,
1206 reg_errcode_t status = REG_OK;
1207 tre_addtags_symbol_t symbol;
1208 tre_ast_node_t *node = tree; /* Tree node we are currently looking at. */
1209 int bottom = tre_stack_num_objects(stack);
1210 /* True for first pass (counting number of needed tags) */
1211 int first_pass = (mem == NULL || tnfa == NULL);
1212 int *regset, *orig_regset;
1213 int num_tags = 0; /* Total number of tags. */
1214 int num_minimals = 0; /* Number of special minimal tags. */
1215 int tag = 0; /* The tag that is to be added next. */
1216 int next_tag = 1; /* Next tag to use after this one. */
1217 int *parents; /* Stack of submatches the current submatch is
1219 int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */
1220 tre_tag_states_t *saved_states;
1222 tre_tag_direction_t direction = TRE_TAG_MINIMIZE;
1226 tnfa->minimal_tags[0] = -1;
1229 regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2));
1233 orig_regset = regset;
1235 parents = xmalloc(sizeof(*parents) * (tnfa->num_submatches + 1));
1236 if (parents == NULL)
1243 saved_states = xmalloc(sizeof(*saved_states) * (tnfa->num_submatches + 1));
1244 if (saved_states == NULL)
1253 for (i = 0; i <= tnfa->num_submatches; i++)
1254 saved_states[i].tag = -1;
1257 STACK_PUSH(stack, voidptr, node);
1258 STACK_PUSH(stack, int, ADDTAGS_RECURSE);
1260 while (tre_stack_num_objects(stack) > bottom)
1262 if (status != REG_OK)
1265 symbol = (tre_addtags_symbol_t)tre_stack_pop_int(stack);
1269 case ADDTAGS_SET_SUBMATCH_END:
1271 int id = tre_stack_pop_int(stack);
1274 /* Add end of this submatch to regset. */
1275 for (i = 0; regset[i] >= 0; i++);
1276 regset[i] = id * 2 + 1;
1279 /* Pop this submatch from the parents stack. */
1280 for (i = 0; parents[i] >= 0; i++);
1281 parents[i - 1] = -1;
1285 case ADDTAGS_RECURSE:
1286 node = tre_stack_pop_voidptr(stack);
1288 if (node->submatch_id >= 0)
1290 int id = node->submatch_id;
1294 /* Add start of this submatch to regset. */
1295 for (i = 0; regset[i] >= 0; i++);
1301 for (i = 0; parents[i] >= 0; i++);
1302 tnfa->submatch_data[id].parents = NULL;
1305 int *p = xmalloc(sizeof(*p) * (i + 1));
1308 status = REG_ESPACE;
1311 assert(tnfa->submatch_data[id].parents == NULL);
1312 tnfa->submatch_data[id].parents = p;
1313 for (i = 0; parents[i] >= 0; i++)
1319 /* Add end of this submatch to regset after processing this
1321 STACK_PUSHX(stack, int, node->submatch_id);
1322 STACK_PUSHX(stack, int, ADDTAGS_SET_SUBMATCH_END);
1329 tre_literal_t *lit = node->obj;
1331 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1336 /* Regset is not empty, so add a tag before the
1337 literal or backref. */
1340 status = tre_add_tag_left(mem, node, tag);
1341 tnfa->tag_directions[tag] = direction;
1342 if (minimal_tag >= 0)
1344 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1345 tnfa->minimal_tags[i] = tag;
1346 tnfa->minimal_tags[i + 1] = minimal_tag;
1347 tnfa->minimal_tags[i + 2] = -1;
1351 tre_purge_regset(regset, tnfa, tag);
1366 assert(!IS_TAG(lit));
1372 tre_catenation_t *cat = node->obj;
1373 tre_ast_node_t *left = cat->left;
1374 tre_ast_node_t *right = cat->right;
1375 int reserved_tag = -1;
1378 /* After processing right child. */
1379 STACK_PUSHX(stack, voidptr, node);
1380 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_RIGHT);
1382 /* Process right child. */
1383 STACK_PUSHX(stack, voidptr, right);
1384 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1386 /* After processing left child. */
1387 STACK_PUSHX(stack, int, next_tag + left->num_tags);
1388 if (left->num_tags > 0 && right->num_tags > 0)
1390 /* Reserve the next tag to the right child. */
1391 reserved_tag = next_tag;
1394 STACK_PUSHX(stack, int, reserved_tag);
1395 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_LEFT);
1397 /* Process left child. */
1398 STACK_PUSHX(stack, voidptr, left);
1399 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1405 tre_iteration_t *iter = node->obj;
1409 STACK_PUSHX(stack, int, regset[0] >= 0 || iter->minimal);
1413 STACK_PUSHX(stack, int, tag);
1414 STACK_PUSHX(stack, int, iter->minimal);
1416 STACK_PUSHX(stack, voidptr, node);
1417 STACK_PUSHX(stack, int, ADDTAGS_AFTER_ITERATION);
1419 STACK_PUSHX(stack, voidptr, iter->arg);
1420 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1422 /* Regset is not empty, so add a tag here. */
1423 if (regset[0] >= 0 || iter->minimal)
1428 status = tre_add_tag_left(mem, node, tag);
1430 tnfa->tag_directions[tag] = TRE_TAG_MAXIMIZE;
1432 tnfa->tag_directions[tag] = direction;
1433 if (minimal_tag >= 0)
1435 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1436 tnfa->minimal_tags[i] = tag;
1437 tnfa->minimal_tags[i + 1] = minimal_tag;
1438 tnfa->minimal_tags[i + 2] = -1;
1442 tre_purge_regset(regset, tnfa, tag);
1450 direction = TRE_TAG_MINIMIZE;
1455 tre_union_t *uni = node->obj;
1456 tre_ast_node_t *left = uni->left;
1457 tre_ast_node_t *right = uni->right;
1463 left_tag = next_tag;
1464 right_tag = next_tag + 1;
1469 right_tag = next_tag;
1472 /* After processing right child. */
1473 STACK_PUSHX(stack, int, right_tag);
1474 STACK_PUSHX(stack, int, left_tag);
1475 STACK_PUSHX(stack, voidptr, regset);
1476 STACK_PUSHX(stack, int, regset[0] >= 0);
1477 STACK_PUSHX(stack, voidptr, node);
1478 STACK_PUSHX(stack, voidptr, right);
1479 STACK_PUSHX(stack, voidptr, left);
1480 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT);
1482 /* Process right child. */
1483 STACK_PUSHX(stack, voidptr, right);
1484 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1486 /* After processing left child. */
1487 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT);
1489 /* Process left child. */
1490 STACK_PUSHX(stack, voidptr, left);
1491 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1493 /* Regset is not empty, so add a tag here. */
1499 status = tre_add_tag_left(mem, node, tag);
1500 tnfa->tag_directions[tag] = direction;
1501 if (minimal_tag >= 0)
1503 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1504 tnfa->minimal_tags[i] = tag;
1505 tnfa->minimal_tags[i + 1] = minimal_tag;
1506 tnfa->minimal_tags[i + 2] = -1;
1510 tre_purge_regset(regset, tnfa, tag);
1519 if (node->num_submatches > 0)
1521 /* The next two tags are reserved for markers. */
1531 if (node->submatch_id >= 0)
1534 /* Push this submatch on the parents stack. */
1535 for (i = 0; parents[i] >= 0; i++);
1536 parents[i] = node->submatch_id;
1537 parents[i + 1] = -1;
1540 break; /* end case: ADDTAGS_RECURSE */
1542 case ADDTAGS_AFTER_ITERATION:
1546 node = tre_stack_pop_voidptr(stack);
1549 node->num_tags = ((tre_iteration_t *)node->obj)->arg->num_tags
1550 + tre_stack_pop_int(stack);
1555 minimal = tre_stack_pop_int(stack);
1556 enter_tag = tre_stack_pop_int(stack);
1558 minimal_tag = enter_tag;
1564 direction = TRE_TAG_MINIMIZE;
1566 direction = TRE_TAG_MAXIMIZE;
1571 case ADDTAGS_AFTER_CAT_LEFT:
1573 int new_tag = tre_stack_pop_int(stack);
1574 next_tag = tre_stack_pop_int(stack);
1582 case ADDTAGS_AFTER_CAT_RIGHT:
1583 node = tre_stack_pop_voidptr(stack);
1585 node->num_tags = ((tre_catenation_t *)node->obj)->left->num_tags
1586 + ((tre_catenation_t *)node->obj)->right->num_tags;
1589 case ADDTAGS_AFTER_UNION_LEFT:
1590 /* Lift the bottom of the `regset' array so that when processing
1591 the right operand the items currently in the array are
1592 invisible. The original bottom was saved at ADDTAGS_UNION and
1593 will be restored at ADDTAGS_AFTER_UNION_RIGHT below. */
1594 while (*regset >= 0)
1598 case ADDTAGS_AFTER_UNION_RIGHT:
1600 int added_tags, tag_left, tag_right;
1601 tre_ast_node_t *left = tre_stack_pop_voidptr(stack);
1602 tre_ast_node_t *right = tre_stack_pop_voidptr(stack);
1603 node = tre_stack_pop_voidptr(stack);
1604 added_tags = tre_stack_pop_int(stack);
1607 node->num_tags = ((tre_union_t *)node->obj)->left->num_tags
1608 + ((tre_union_t *)node->obj)->right->num_tags + added_tags
1609 + ((node->num_submatches > 0) ? 2 : 0);
1611 regset = tre_stack_pop_voidptr(stack);
1612 tag_left = tre_stack_pop_int(stack);
1613 tag_right = tre_stack_pop_int(stack);
1615 /* Add tags after both children, the left child gets a smaller
1616 tag than the right child. This guarantees that we prefer
1617 the left child over the right child. */
1618 /* XXX - This is not always necessary (if the children have
1619 tags which must be seen for every match of that child). */
1620 /* XXX - Check if this is the only place where tre_add_tag_right
1621 is used. If so, use tre_add_tag_left (putting the tag before
1622 the child as opposed after the child) and throw away
1623 tre_add_tag_right. */
1624 if (node->num_submatches > 0)
1628 status = tre_add_tag_right(mem, left, tag_left);
1629 tnfa->tag_directions[tag_left] = TRE_TAG_MAXIMIZE;
1630 if (status == REG_OK)
1631 status = tre_add_tag_right(mem, right, tag_right);
1632 tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE;
1636 direction = TRE_TAG_MAXIMIZE;
1644 } /* end switch(symbol) */
1645 } /* end while(tre_stack_num_objects(stack) > bottom) */
1648 tre_purge_regset(regset, tnfa, tag);
1650 if (!first_pass && minimal_tag >= 0)
1653 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1654 tnfa->minimal_tags[i] = tag;
1655 tnfa->minimal_tags[i + 1] = minimal_tag;
1656 tnfa->minimal_tags[i + 2] = -1;
1661 assert(tree->num_tags == num_tags);
1662 tnfa->end_tag = num_tags;
1663 tnfa->num_tags = num_tags;
1664 tnfa->num_minimals = num_minimals;
1667 xfree(saved_states);
1674 AST to TNFA compilation routines.
1680 } tre_copyast_symbol_t;
1682 /* Flags for tre_copy_ast(). */
1683 #define COPY_REMOVE_TAGS 1
1684 #define COPY_MAXIMIZE_FIRST_TAG 2
1686 static reg_errcode_t
1687 tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
1688 int flags, int *pos_add, tre_tag_direction_t *tag_directions,
1689 tre_ast_node_t **copy, int *max_pos)
1691 reg_errcode_t status = REG_OK;
1692 int bottom = tre_stack_num_objects(stack);
1695 tre_ast_node_t **result = copy;
1696 tre_copyast_symbol_t symbol;
1698 STACK_PUSH(stack, voidptr, ast);
1699 STACK_PUSH(stack, int, COPY_RECURSE);
1701 while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
1703 tre_ast_node_t *node;
1704 if (status != REG_OK)
1707 symbol = (tre_copyast_symbol_t)tre_stack_pop_int(stack);
1710 case COPY_SET_RESULT_PTR:
1711 result = tre_stack_pop_voidptr(stack);
1714 node = tre_stack_pop_voidptr(stack);
1719 tre_literal_t *lit = node->obj;
1720 int pos = lit->position;
1721 int min = lit->code_min;
1722 int max = lit->code_max;
1723 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1725 /* XXX - e.g. [ab] has only one position but two
1726 nodes, so we are creating holes in the state space
1727 here. Not fatal, just wastes memory. */
1731 else if (IS_TAG(lit) && (flags & COPY_REMOVE_TAGS))
1733 /* Change this tag to empty. */
1737 else if (IS_TAG(lit) && (flags & COPY_MAXIMIZE_FIRST_TAG)
1740 /* Maximize the first tag. */
1741 tag_directions[max] = TRE_TAG_MAXIMIZE;
1744 *result = tre_ast_new_literal(mem, min, max, pos);
1745 if (*result == NULL)
1746 status = REG_ESPACE;
1748 tre_literal_t *p = (*result)->obj;
1749 p->class = lit->class;
1750 p->neg_classes = lit->neg_classes;
1759 tre_union_t *uni = node->obj;
1761 *result = tre_ast_new_union(mem, uni->left, uni->right);
1762 if (*result == NULL)
1764 status = REG_ESPACE;
1767 tmp = (*result)->obj;
1768 result = &tmp->left;
1769 STACK_PUSHX(stack, voidptr, uni->right);
1770 STACK_PUSHX(stack, int, COPY_RECURSE);
1771 STACK_PUSHX(stack, voidptr, &tmp->right);
1772 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
1773 STACK_PUSHX(stack, voidptr, uni->left);
1774 STACK_PUSHX(stack, int, COPY_RECURSE);
1779 tre_catenation_t *cat = node->obj;
1780 tre_catenation_t *tmp;
1781 *result = tre_ast_new_catenation(mem, cat->left, cat->right);
1782 if (*result == NULL)
1784 status = REG_ESPACE;
1787 tmp = (*result)->obj;
1790 result = &tmp->left;
1792 STACK_PUSHX(stack, voidptr, cat->right);
1793 STACK_PUSHX(stack, int, COPY_RECURSE);
1794 STACK_PUSHX(stack, voidptr, &tmp->right);
1795 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
1796 STACK_PUSHX(stack, voidptr, cat->left);
1797 STACK_PUSHX(stack, int, COPY_RECURSE);
1802 tre_iteration_t *iter = node->obj;
1803 STACK_PUSHX(stack, voidptr, iter->arg);
1804 STACK_PUSHX(stack, int, COPY_RECURSE);
1805 *result = tre_ast_new_iter(mem, iter->arg, iter->min,
1806 iter->max, iter->minimal);
1807 if (*result == NULL)
1809 status = REG_ESPACE;
1812 iter = (*result)->obj;
1813 result = &iter->arg;
1823 *pos_add += num_copied;
1830 } tre_expand_ast_symbol_t;
1832 /* Expands each iteration node that has a finite nonzero minimum or maximum
1833 iteration count to a catenated sequence of copies of the node. */
1834 static reg_errcode_t
1835 tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
1836 int *position, tre_tag_direction_t *tag_directions)
1838 reg_errcode_t status = REG_OK;
1839 int bottom = tre_stack_num_objects(stack);
1841 int pos_add_total = 0;
1845 STACK_PUSHR(stack, voidptr, ast);
1846 STACK_PUSHR(stack, int, EXPAND_RECURSE);
1847 while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
1849 tre_ast_node_t *node;
1850 tre_expand_ast_symbol_t symbol;
1852 if (status != REG_OK)
1855 symbol = (tre_expand_ast_symbol_t)tre_stack_pop_int(stack);
1856 node = tre_stack_pop_voidptr(stack);
1859 case EXPAND_RECURSE:
1864 tre_literal_t *lit= node->obj;
1865 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1867 lit->position += pos_add;
1868 if (lit->position > max_pos)
1869 max_pos = lit->position;
1875 tre_union_t *uni = node->obj;
1876 STACK_PUSHX(stack, voidptr, uni->right);
1877 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1878 STACK_PUSHX(stack, voidptr, uni->left);
1879 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1884 tre_catenation_t *cat = node->obj;
1885 STACK_PUSHX(stack, voidptr, cat->right);
1886 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1887 STACK_PUSHX(stack, voidptr, cat->left);
1888 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1893 tre_iteration_t *iter = node->obj;
1894 STACK_PUSHX(stack, int, pos_add);
1895 STACK_PUSHX(stack, voidptr, node);
1896 STACK_PUSHX(stack, int, EXPAND_AFTER_ITER);
1897 STACK_PUSHX(stack, voidptr, iter->arg);
1898 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1899 /* If we are going to expand this node at EXPAND_AFTER_ITER
1900 then don't increase the `pos' fields of the nodes now, it
1901 will get done when expanding. */
1902 if (iter->min > 1 || iter->max > 1)
1912 case EXPAND_AFTER_ITER:
1914 tre_iteration_t *iter = node->obj;
1916 pos_add = tre_stack_pop_int(stack);
1917 pos_add_last = pos_add;
1918 if (iter->min > 1 || iter->max > 1)
1920 tre_ast_node_t *seq1 = NULL, *seq2 = NULL;
1922 int pos_add_save = pos_add;
1924 /* Create a catenated sequence of copies of the node. */
1925 for (j = 0; j < iter->min; j++)
1927 tre_ast_node_t *copy;
1928 /* Remove tags from all but the last copy. */
1929 int flags = ((j + 1 < iter->min)
1931 : COPY_MAXIMIZE_FIRST_TAG);
1932 pos_add_save = pos_add;
1933 status = tre_copy_ast(mem, stack, iter->arg, flags,
1934 &pos_add, tag_directions, ©,
1936 if (status != REG_OK)
1939 seq1 = tre_ast_new_catenation(mem, seq1, copy);
1946 if (iter->max == -1)
1948 /* No upper limit. */
1949 pos_add_save = pos_add;
1950 status = tre_copy_ast(mem, stack, iter->arg, 0,
1951 &pos_add, NULL, &seq2, &max_pos);
1952 if (status != REG_OK)
1954 seq2 = tre_ast_new_iter(mem, seq2, 0, -1, 0);
1960 for (j = iter->min; j < iter->max; j++)
1962 tre_ast_node_t *tmp, *copy;
1963 pos_add_save = pos_add;
1964 status = tre_copy_ast(mem, stack, iter->arg, 0,
1965 &pos_add, NULL, ©, &max_pos);
1966 if (status != REG_OK)
1969 seq2 = tre_ast_new_catenation(mem, copy, seq2);
1974 tmp = tre_ast_new_literal(mem, EMPTY, -1, -1);
1977 seq2 = tre_ast_new_union(mem, tmp, seq2);
1983 pos_add = pos_add_save;
1986 else if (seq2 != NULL)
1987 seq1 = tre_ast_new_catenation(mem, seq1, seq2);
1990 node->obj = seq1->obj;
1991 node->type = seq1->type;
1995 pos_add_total += pos_add - pos_add_last;
1996 if (iter_depth == 0)
1997 pos_add = pos_add_total;
2007 *position += pos_add_total;
2009 /* `max_pos' should never be larger than `*position' if the above
2010 code works, but just an extra safeguard let's make sure
2011 `*position' is set large enough so enough memory will be
2012 allocated for the transition table. */
2013 if (max_pos > *position)
2014 *position = max_pos;
2019 static tre_pos_and_tags_t *
2020 tre_set_empty(tre_mem_t mem)
2022 tre_pos_and_tags_t *new_set;
2024 new_set = tre_mem_calloc(mem, sizeof(*new_set));
2025 if (new_set == NULL)
2028 new_set[0].position = -1;
2029 new_set[0].code_min = -1;
2030 new_set[0].code_max = -1;
2035 static tre_pos_and_tags_t *
2036 tre_set_one(tre_mem_t mem, int position, int code_min, int code_max,
2037 tre_ctype_t class, tre_ctype_t *neg_classes, int backref)
2039 tre_pos_and_tags_t *new_set;
2041 new_set = tre_mem_calloc(mem, sizeof(*new_set) * 2);
2042 if (new_set == NULL)
2045 new_set[0].position = position;
2046 new_set[0].code_min = code_min;
2047 new_set[0].code_max = code_max;
2048 new_set[0].class = class;
2049 new_set[0].neg_classes = neg_classes;
2050 new_set[0].backref = backref;
2051 new_set[1].position = -1;
2052 new_set[1].code_min = -1;
2053 new_set[1].code_max = -1;
2058 static tre_pos_and_tags_t *
2059 tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2,
2060 int *tags, int assertions)
2063 tre_pos_and_tags_t *new_set;
2067 for (num_tags = 0; tags != NULL && tags[num_tags] >= 0; num_tags++);
2068 for (s1 = 0; set1[s1].position >= 0; s1++);
2069 for (s2 = 0; set2[s2].position >= 0; s2++);
2070 new_set = tre_mem_calloc(mem, sizeof(*new_set) * (s1 + s2 + 1));
2074 for (s1 = 0; set1[s1].position >= 0; s1++)
2076 new_set[s1].position = set1[s1].position;
2077 new_set[s1].code_min = set1[s1].code_min;
2078 new_set[s1].code_max = set1[s1].code_max;
2079 new_set[s1].assertions = set1[s1].assertions | assertions;
2080 new_set[s1].class = set1[s1].class;
2081 new_set[s1].neg_classes = set1[s1].neg_classes;
2082 new_set[s1].backref = set1[s1].backref;
2083 if (set1[s1].tags == NULL && tags == NULL)
2084 new_set[s1].tags = NULL;
2087 for (i = 0; set1[s1].tags != NULL && set1[s1].tags[i] >= 0; i++);
2088 new_tags = tre_mem_alloc(mem, (sizeof(*new_tags)
2089 * (i + num_tags + 1)));
2090 if (new_tags == NULL)
2092 for (j = 0; j < i; j++)
2093 new_tags[j] = set1[s1].tags[j];
2094 for (i = 0; i < num_tags; i++)
2095 new_tags[j + i] = tags[i];
2096 new_tags[j + i] = -1;
2097 new_set[s1].tags = new_tags;
2101 for (s2 = 0; set2[s2].position >= 0; s2++)
2103 new_set[s1 + s2].position = set2[s2].position;
2104 new_set[s1 + s2].code_min = set2[s2].code_min;
2105 new_set[s1 + s2].code_max = set2[s2].code_max;
2106 /* XXX - why not | assertions here as well? */
2107 new_set[s1 + s2].assertions = set2[s2].assertions;
2108 new_set[s1 + s2].class = set2[s2].class;
2109 new_set[s1 + s2].neg_classes = set2[s2].neg_classes;
2110 new_set[s1 + s2].backref = set2[s2].backref;
2111 if (set2[s2].tags == NULL)
2112 new_set[s1 + s2].tags = NULL;
2115 for (i = 0; set2[s2].tags[i] >= 0; i++);
2116 new_tags = tre_mem_alloc(mem, sizeof(*new_tags) * (i + 1));
2117 if (new_tags == NULL)
2119 for (j = 0; j < i; j++)
2120 new_tags[j] = set2[s2].tags[j];
2122 new_set[s1 + s2].tags = new_tags;
2125 new_set[s1 + s2].position = -1;
2129 /* Finds the empty path through `node' which is the one that should be
2130 taken according to POSIX.2 rules, and adds the tags on that path to
2131 `tags'. `tags' may be NULL. If `num_tags_seen' is not NULL, it is
2132 set to the number of tags seen on the path. */
2133 static reg_errcode_t
2134 tre_match_empty(tre_stack_t *stack, tre_ast_node_t *node, int *tags,
2135 int *assertions, int *num_tags_seen)
2139 tre_catenation_t *cat;
2140 tre_iteration_t *iter;
2142 int bottom = tre_stack_num_objects(stack);
2143 reg_errcode_t status = REG_OK;
2147 status = tre_stack_push_voidptr(stack, node);
2149 /* Walk through the tree recursively. */
2150 while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2152 node = tre_stack_pop_voidptr(stack);
2157 lit = (tre_literal_t *)node->obj;
2158 switch (lit->code_min)
2161 if (lit->code_max >= 0)
2165 /* Add the tag to `tags'. */
2166 for (i = 0; tags[i] >= 0; i++)
2167 if (tags[i] == lit->code_max)
2171 tags[i] = lit->code_max;
2180 assert(lit->code_max >= 1
2181 || lit->code_max <= ASSERT_LAST);
2182 if (assertions != NULL)
2183 *assertions |= lit->code_max;
2194 /* Subexpressions starting earlier take priority over ones
2195 starting later, so we prefer the left subexpression over the
2196 right subexpression. */
2197 uni = (tre_union_t *)node->obj;
2198 if (uni->left->nullable)
2199 STACK_PUSHX(stack, voidptr, uni->left)
2200 else if (uni->right->nullable)
2201 STACK_PUSHX(stack, voidptr, uni->right)
2207 /* The path must go through both children. */
2208 cat = (tre_catenation_t *)node->obj;
2209 assert(cat->left->nullable);
2210 assert(cat->right->nullable);
2211 STACK_PUSHX(stack, voidptr, cat->left);
2212 STACK_PUSHX(stack, voidptr, cat->right);
2216 /* A match with an empty string is preferred over no match at
2217 all, so we go through the argument if possible. */
2218 iter = (tre_iteration_t *)node->obj;
2219 if (iter->arg->nullable)
2220 STACK_PUSHX(stack, voidptr, iter->arg);
2236 NFL_POST_CATENATION,
2238 } tre_nfl_stack_symbol_t;
2241 /* Computes and fills in the fields `nullable', `firstpos', and `lastpos' for
2242 the nodes of the AST `tree'. */
2243 static reg_errcode_t
2244 tre_compute_nfl(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree)
2246 int bottom = tre_stack_num_objects(stack);
2248 STACK_PUSHR(stack, voidptr, tree);
2249 STACK_PUSHR(stack, int, NFL_RECURSE);
2251 while (tre_stack_num_objects(stack) > bottom)
2253 tre_nfl_stack_symbol_t symbol;
2254 tre_ast_node_t *node;
2256 symbol = (tre_nfl_stack_symbol_t)tre_stack_pop_int(stack);
2257 node = tre_stack_pop_voidptr(stack);
2265 tre_literal_t *lit = (tre_literal_t *)node->obj;
2266 if (IS_BACKREF(lit))
2268 /* Back references: nullable = false, firstpos = {i},
2271 node->firstpos = tre_set_one(mem, lit->position, 0,
2272 TRE_CHAR_MAX, 0, NULL, -1);
2273 if (!node->firstpos)
2275 node->lastpos = tre_set_one(mem, lit->position, 0,
2276 TRE_CHAR_MAX, 0, NULL,
2277 (int)lit->code_max);
2281 else if (lit->code_min < 0)
2283 /* Tags, empty strings, params, and zero width assertions:
2284 nullable = true, firstpos = {}, and lastpos = {}. */
2286 node->firstpos = tre_set_empty(mem);
2287 if (!node->firstpos)
2289 node->lastpos = tre_set_empty(mem);
2295 /* Literal at position i: nullable = false, firstpos = {i},
2299 tre_set_one(mem, lit->position, (int)lit->code_min,
2300 (int)lit->code_max, 0, NULL, -1);
2301 if (!node->firstpos)
2303 node->lastpos = tre_set_one(mem, lit->position,
2306 lit->class, lit->neg_classes,
2315 /* Compute the attributes for the two subtrees, and after that
2317 STACK_PUSHR(stack, voidptr, node);
2318 STACK_PUSHR(stack, int, NFL_POST_UNION);
2319 STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->right);
2320 STACK_PUSHR(stack, int, NFL_RECURSE);
2321 STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->left);
2322 STACK_PUSHR(stack, int, NFL_RECURSE);
2326 /* Compute the attributes for the two subtrees, and after that
2328 STACK_PUSHR(stack, voidptr, node);
2329 STACK_PUSHR(stack, int, NFL_POST_CATENATION);
2330 STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->right);
2331 STACK_PUSHR(stack, int, NFL_RECURSE);
2332 STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->left);
2333 STACK_PUSHR(stack, int, NFL_RECURSE);
2337 /* Compute the attributes for the subtree, and after that for
2339 STACK_PUSHR(stack, voidptr, node);
2340 STACK_PUSHR(stack, int, NFL_POST_ITERATION);
2341 STACK_PUSHR(stack, voidptr, ((tre_iteration_t *)node->obj)->arg);
2342 STACK_PUSHR(stack, int, NFL_RECURSE);
2345 break; /* end case: NFL_RECURSE */
2347 case NFL_POST_UNION:
2349 tre_union_t *uni = (tre_union_t *)node->obj;
2350 node->nullable = uni->left->nullable || uni->right->nullable;
2351 node->firstpos = tre_set_union(mem, uni->left->firstpos,
2352 uni->right->firstpos, NULL, 0);
2353 if (!node->firstpos)
2355 node->lastpos = tre_set_union(mem, uni->left->lastpos,
2356 uni->right->lastpos, NULL, 0);
2362 case NFL_POST_ITERATION:
2364 tre_iteration_t *iter = (tre_iteration_t *)node->obj;
2366 if (iter->min == 0 || iter->arg->nullable)
2370 node->firstpos = iter->arg->firstpos;
2371 node->lastpos = iter->arg->lastpos;
2375 case NFL_POST_CATENATION:
2377 int num_tags, *tags, assertions;
2378 reg_errcode_t status;
2379 tre_catenation_t *cat = node->obj;
2380 node->nullable = cat->left->nullable && cat->right->nullable;
2382 /* Compute firstpos. */
2383 if (cat->left->nullable)
2385 /* The left side matches the empty string. Make a first pass
2386 with tre_match_empty() to get the number of tags and
2388 status = tre_match_empty(stack, cat->left,
2389 NULL, NULL, &num_tags);
2390 if (status != REG_OK)
2392 /* Allocate arrays for the tags and parameters. */
2393 tags = xmalloc(sizeof(*tags) * (num_tags + 1));
2398 /* Second pass with tre_mach_empty() to get the list of
2399 tags and parameters. */
2400 status = tre_match_empty(stack, cat->left, tags,
2402 if (status != REG_OK)
2408 tre_set_union(mem, cat->right->firstpos, cat->left->firstpos,
2411 if (!node->firstpos)
2416 node->firstpos = cat->left->firstpos;
2419 /* Compute lastpos. */
2420 if (cat->right->nullable)
2422 /* The right side matches the empty string. Make a first pass
2423 with tre_match_empty() to get the number of tags and
2425 status = tre_match_empty(stack, cat->right,
2426 NULL, NULL, &num_tags);
2427 if (status != REG_OK)
2429 /* Allocate arrays for the tags and parameters. */
2430 tags = xmalloc(sizeof(int) * (num_tags + 1));
2435 /* Second pass with tre_mach_empty() to get the list of
2436 tags and parameters. */
2437 status = tre_match_empty(stack, cat->right, tags,
2439 if (status != REG_OK)
2445 tre_set_union(mem, cat->left->lastpos, cat->right->lastpos,
2453 node->lastpos = cat->right->lastpos;
2468 /* Adds a transition from each position in `p1' to each position in `p2'. */
2469 static reg_errcode_t
2470 tre_make_trans(tre_pos_and_tags_t *p1, tre_pos_and_tags_t *p2,
2471 tre_tnfa_transition_t *transitions,
2472 int *counts, int *offs)
2474 tre_pos_and_tags_t *orig_p2 = p2;
2475 tre_tnfa_transition_t *trans;
2476 int i, j, k, l, dup, prev_p2_pos;
2478 if (transitions != NULL)
2479 while (p1->position >= 0)
2483 while (p2->position >= 0)
2485 /* Optimization: if this position was already handled, skip it. */
2486 if (p2->position == prev_p2_pos)
2491 prev_p2_pos = p2->position;
2492 /* Set `trans' to point to the next unused transition from
2493 position `p1->position'. */
2494 trans = transitions + offs[p1->position];
2495 while (trans->state != NULL)
2498 /* If we find a previous transition from `p1->position' to
2499 `p2->position', it is overwritten. This can happen only
2500 if there are nested loops in the regexp, like in "((a)*)*".
2501 In POSIX.2 repetition using the outer loop is always
2502 preferred over using the inner loop. Therefore the
2503 transition for the inner loop is useless and can be thrown
2505 /* XXX - The same position is used for all nodes in a bracket
2506 expression, so this optimization cannot be used (it will
2507 break bracket expressions) unless I figure out a way to
2509 if (trans->state_id == p2->position)
2517 if (trans->state == NULL)
2518 (trans + 1)->state = NULL;
2519 /* Use the character ranges, assertions, etc. from `p1' for
2520 the transition from `p1' to `p2'. */
2521 trans->code_min = p1->code_min;
2522 trans->code_max = p1->code_max;
2523 trans->state = transitions + offs[p2->position];
2524 trans->state_id = p2->position;
2525 trans->assertions = p1->assertions | p2->assertions
2526 | (p1->class ? ASSERT_CHAR_CLASS : 0)
2527 | (p1->neg_classes != NULL ? ASSERT_CHAR_CLASS_NEG : 0);
2528 if (p1->backref >= 0)
2530 assert((trans->assertions & ASSERT_CHAR_CLASS) == 0);
2531 assert(p2->backref < 0);
2532 trans->u.backref = p1->backref;
2533 trans->assertions |= ASSERT_BACKREF;
2536 trans->u.class = p1->class;
2537 if (p1->neg_classes != NULL)
2539 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++);
2540 trans->neg_classes =
2541 xmalloc(sizeof(*trans->neg_classes) * (i + 1));
2542 if (trans->neg_classes == NULL)
2544 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++)
2545 trans->neg_classes[i] = p1->neg_classes[i];
2546 trans->neg_classes[i] = (tre_ctype_t)0;
2549 trans->neg_classes = NULL;
2551 /* Find out how many tags this transition has. */
2553 if (p1->tags != NULL)
2554 while(p1->tags[i] >= 0)
2557 if (p2->tags != NULL)
2558 while(p2->tags[j] >= 0)
2561 /* If we are overwriting a transition, free the old tag array. */
2562 if (trans->tags != NULL)
2566 /* If there were any tags, allocate an array and fill it. */
2569 trans->tags = xmalloc(sizeof(*trans->tags) * (i + j + 1));
2573 if (p1->tags != NULL)
2574 while(p1->tags[i] >= 0)
2576 trans->tags[i] = p1->tags[i];
2581 if (p2->tags != NULL)
2582 while (p2->tags[j] >= 0)
2584 /* Don't add duplicates. */
2586 for (k = 0; k < i; k++)
2587 if (trans->tags[k] == p2->tags[j])
2593 trans->tags[l++] = p2->tags[j];
2596 trans->tags[l] = -1;
2604 /* Compute a maximum limit for the number of transitions leaving
2606 while (p1->position >= 0)
2609 while (p2->position >= 0)
2611 counts[p1->position]++;
2619 /* Converts the syntax tree to a TNFA. All the transitions in the TNFA are
2620 labelled with one character range (there are no transitions on empty
2621 strings). The TNFA takes O(n^2) space in the worst case, `n' is size of
2623 static reg_errcode_t
2624 tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions,
2625 int *counts, int *offs)
2628 tre_catenation_t *cat;
2629 tre_iteration_t *iter;
2630 reg_errcode_t errcode = REG_OK;
2632 /* XXX - recurse using a stack!. */
2638 uni = (tre_union_t *)node->obj;
2639 errcode = tre_ast_to_tnfa(uni->left, transitions, counts, offs);
2640 if (errcode != REG_OK)
2642 errcode = tre_ast_to_tnfa(uni->right, transitions, counts, offs);
2646 cat = (tre_catenation_t *)node->obj;
2647 /* Add a transition from each position in cat->left->lastpos
2648 to each position in cat->right->firstpos. */
2649 errcode = tre_make_trans(cat->left->lastpos, cat->right->firstpos,
2650 transitions, counts, offs);
2651 if (errcode != REG_OK)
2653 errcode = tre_ast_to_tnfa(cat->left, transitions, counts, offs);
2654 if (errcode != REG_OK)
2656 errcode = tre_ast_to_tnfa(cat->right, transitions, counts, offs);
2660 iter = (tre_iteration_t *)node->obj;
2661 assert(iter->max == -1 || iter->max == 1);
2663 if (iter->max == -1)
2665 assert(iter->min == 0 || iter->min == 1);
2666 /* Add a transition from each last position in the iterated
2667 expression to each first position. */
2668 errcode = tre_make_trans(iter->arg->lastpos, iter->arg->firstpos,
2669 transitions, counts, offs);
2670 if (errcode != REG_OK)
2673 errcode = tre_ast_to_tnfa(iter->arg, transitions, counts, offs);
2680 #define ERROR_EXIT(err) \
2684 if (/*CONSTCOND*/1) \
2687 while (/*CONSTCOND*/0)
2691 regcomp(regex_t *restrict preg, const char *restrict regex, int cflags)
2694 tre_ast_node_t *tree, *tmp_ast_l, *tmp_ast_r;
2695 tre_pos_and_tags_t *p;
2696 int *counts = NULL, *offs = NULL;
2698 tre_tnfa_transition_t *transitions, *initial;
2699 tre_tnfa_t *tnfa = NULL;
2700 tre_submatch_data_t *submatch_data;
2701 tre_tag_direction_t *tag_directions = NULL;
2702 reg_errcode_t errcode;
2705 /* Parse context. */
2706 tre_parse_ctx_t parse_ctx;
2708 /* Allocate a stack used throughout the compilation process for various
2710 stack = tre_stack_new(512, 1024000, 128);
2713 /* Allocate a fast memory allocator. */
2714 mem = tre_mem_new();
2717 tre_stack_destroy(stack);
2721 /* Parse the regexp. */
2722 memset(&parse_ctx, 0, sizeof(parse_ctx));
2723 parse_ctx.mem = mem;
2724 parse_ctx.stack = stack;
2725 parse_ctx.start = regex;
2726 parse_ctx.cflags = cflags;
2727 parse_ctx.max_backref = -1;
2728 errcode = tre_parse(&parse_ctx);
2729 if (errcode != REG_OK)
2730 ERROR_EXIT(errcode);
2731 preg->re_nsub = parse_ctx.submatch_id - 1;
2735 tre_ast_print(tree);
2736 #endif /* TRE_DEBUG */
2738 /* Referring to nonexistent subexpressions is illegal. */
2739 if (parse_ctx.max_backref > (int)preg->re_nsub)
2740 ERROR_EXIT(REG_ESUBREG);
2742 /* Allocate the TNFA struct. */
2743 tnfa = xcalloc(1, sizeof(tre_tnfa_t));
2745 ERROR_EXIT(REG_ESPACE);
2746 tnfa->have_backrefs = parse_ctx.max_backref >= 0;
2747 tnfa->have_approx = 0;
2748 tnfa->num_submatches = parse_ctx.submatch_id;
2750 /* Set up tags for submatch addressing. If REG_NOSUB is set and the
2751 regexp does not have back references, this can be skipped. */
2752 if (tnfa->have_backrefs || !(cflags & REG_NOSUB))
2755 /* Figure out how many tags we will need. */
2756 errcode = tre_add_tags(NULL, stack, tree, tnfa);
2757 if (errcode != REG_OK)
2758 ERROR_EXIT(errcode);
2760 if (tnfa->num_tags > 0)
2762 tag_directions = xmalloc(sizeof(*tag_directions)
2763 * (tnfa->num_tags + 1));
2764 if (tag_directions == NULL)
2765 ERROR_EXIT(REG_ESPACE);
2766 tnfa->tag_directions = tag_directions;
2767 memset(tag_directions, -1,
2768 sizeof(*tag_directions) * (tnfa->num_tags + 1));
2770 tnfa->minimal_tags = xcalloc((unsigned)tnfa->num_tags * 2 + 1,
2771 sizeof(*tnfa->minimal_tags));
2772 if (tnfa->minimal_tags == NULL)
2773 ERROR_EXIT(REG_ESPACE);
2775 submatch_data = xcalloc((unsigned)parse_ctx.submatch_id,
2776 sizeof(*submatch_data));
2777 if (submatch_data == NULL)
2778 ERROR_EXIT(REG_ESPACE);
2779 tnfa->submatch_data = submatch_data;
2781 errcode = tre_add_tags(mem, stack, tree, tnfa);
2782 if (errcode != REG_OK)
2783 ERROR_EXIT(errcode);
2787 /* Expand iteration nodes. */
2788 errcode = tre_expand_ast(mem, stack, tree, &parse_ctx.position,
2790 if (errcode != REG_OK)
2791 ERROR_EXIT(errcode);
2793 /* Add a dummy node for the final state.
2794 XXX - For certain patterns this dummy node can be optimized away,
2795 for example "a*" or "ab*". Figure out a simple way to detect
2796 this possibility. */
2798 tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position++);
2799 if (tmp_ast_r == NULL)
2800 ERROR_EXIT(REG_ESPACE);
2802 tree = tre_ast_new_catenation(mem, tmp_ast_l, tmp_ast_r);
2804 ERROR_EXIT(REG_ESPACE);
2806 errcode = tre_compute_nfl(mem, stack, tree);
2807 if (errcode != REG_OK)
2808 ERROR_EXIT(errcode);
2810 counts = xmalloc(sizeof(int) * parse_ctx.position);
2812 ERROR_EXIT(REG_ESPACE);
2814 offs = xmalloc(sizeof(int) * parse_ctx.position);
2816 ERROR_EXIT(REG_ESPACE);
2818 for (i = 0; i < parse_ctx.position; i++)
2820 tre_ast_to_tnfa(tree, NULL, counts, NULL);
2823 for (i = 0; i < parse_ctx.position; i++)
2826 add += counts[i] + 1;
2829 transitions = xcalloc((unsigned)add + 1, sizeof(*transitions));
2830 if (transitions == NULL)
2831 ERROR_EXIT(REG_ESPACE);
2832 tnfa->transitions = transitions;
2833 tnfa->num_transitions = add;
2835 errcode = tre_ast_to_tnfa(tree, transitions, counts, offs);
2836 if (errcode != REG_OK)
2837 ERROR_EXIT(errcode);
2839 tnfa->firstpos_chars = NULL;
2843 while (p->position >= 0)
2849 initial = xcalloc((unsigned)i + 1, sizeof(tre_tnfa_transition_t));
2850 if (initial == NULL)
2851 ERROR_EXIT(REG_ESPACE);
2852 tnfa->initial = initial;
2855 for (p = tree->firstpos; p->position >= 0; p++)
2857 initial[i].state = transitions + offs[p->position];
2858 initial[i].state_id = p->position;
2859 initial[i].tags = NULL;
2860 /* Copy the arrays p->tags, and p->params, they are allocated
2861 from a tre_mem object. */
2865 for (j = 0; p->tags[j] >= 0; j++);
2866 initial[i].tags = xmalloc(sizeof(*p->tags) * (j + 1));
2867 if (!initial[i].tags)
2868 ERROR_EXIT(REG_ESPACE);
2869 memcpy(initial[i].tags, p->tags, sizeof(*p->tags) * (j + 1));
2871 initial[i].assertions = p->assertions;
2874 initial[i].state = NULL;
2876 tnfa->num_transitions = add;
2877 tnfa->final = transitions + offs[tree->lastpos[0].position];
2878 tnfa->num_states = parse_ctx.position;
2879 tnfa->cflags = cflags;
2881 tre_mem_destroy(mem);
2882 tre_stack_destroy(stack);
2886 preg->TRE_REGEX_T_FIELD = (void *)tnfa;
2890 /* Free everything that was allocated and return the error code. */
2891 tre_mem_destroy(mem);
2893 tre_stack_destroy(stack);
2898 preg->TRE_REGEX_T_FIELD = (void *)tnfa;
2907 regfree(regex_t *preg)
2911 tre_tnfa_transition_t *trans;
2913 tnfa = (void *)preg->TRE_REGEX_T_FIELD;
2917 for (i = 0; i < tnfa->num_transitions; i++)
2918 if (tnfa->transitions[i].state)
2920 if (tnfa->transitions[i].tags)
2921 xfree(tnfa->transitions[i].tags);
2922 if (tnfa->transitions[i].neg_classes)
2923 xfree(tnfa->transitions[i].neg_classes);
2925 if (tnfa->transitions)
2926 xfree(tnfa->transitions);
2930 for (trans = tnfa->initial; trans->state; trans++)
2935 xfree(tnfa->initial);
2938 if (tnfa->submatch_data)
2940 for (i = 0; i < tnfa->num_submatches; i++)
2941 if (tnfa->submatch_data[i].parents)
2942 xfree(tnfa->submatch_data[i].parents);
2943 xfree(tnfa->submatch_data);
2946 if (tnfa->tag_directions)
2947 xfree(tnfa->tag_directions);
2948 if (tnfa->firstpos_chars)
2949 xfree(tnfa->firstpos_chars);
2950 if (tnfa->minimal_tags)
2951 xfree(tnfa->minimal_tags);