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