2 regexec.c - TRE POSIX compatible matching functions (and more).
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.
45 tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
46 const tre_tnfa_t *tnfa, int *tags, int match_eo);
48 /***********************************************************************
49 from tre-match-utils.h
50 ***********************************************************************/
52 #define GET_NEXT_WCHAR() do { \
53 prev_c = next_c; pos += pos_add_next; \
54 if ((pos_add_next = mbtowc(&next_c, str_byte, MB_LEN_MAX)) <= 0) { \
55 if (pos_add_next < 0) { ret = REG_NOMATCH; goto error_exit; } \
56 else pos_add_next++; \
58 str_byte += pos_add_next; \
61 #define IS_WORD_CHAR(c) ((c) == L'_' || tre_isalnum(c))
63 #define CHECK_ASSERTIONS(assertions) \
64 (((assertions & ASSERT_AT_BOL) \
65 && (pos > 0 || reg_notbol) \
66 && (prev_c != L'\n' || !reg_newline)) \
67 || ((assertions & ASSERT_AT_EOL) \
68 && (next_c != L'\0' || reg_noteol) \
69 && (next_c != L'\n' || !reg_newline)) \
70 || ((assertions & ASSERT_AT_BOW) \
71 && (IS_WORD_CHAR(prev_c) || !IS_WORD_CHAR(next_c))) \
72 || ((assertions & ASSERT_AT_EOW) \
73 && (!IS_WORD_CHAR(prev_c) || IS_WORD_CHAR(next_c))) \
74 || ((assertions & ASSERT_AT_WB) \
75 && (pos != 0 && next_c != L'\0' \
76 && IS_WORD_CHAR(prev_c) == IS_WORD_CHAR(next_c))) \
77 || ((assertions & ASSERT_AT_WB_NEG) \
78 && (pos == 0 || next_c == L'\0' \
79 || IS_WORD_CHAR(prev_c) != IS_WORD_CHAR(next_c))))
81 #define CHECK_CHAR_CLASSES(trans_i, tnfa, eflags) \
82 (((trans_i->assertions & ASSERT_CHAR_CLASS) \
83 && !(tnfa->cflags & REG_ICASE) \
84 && !tre_isctype((tre_cint_t)prev_c, trans_i->u.class)) \
85 || ((trans_i->assertions & ASSERT_CHAR_CLASS) \
86 && (tnfa->cflags & REG_ICASE) \
87 && !tre_isctype(tre_tolower((tre_cint_t)prev_c),trans_i->u.class) \
88 && !tre_isctype(tre_toupper((tre_cint_t)prev_c),trans_i->u.class)) \
89 || ((trans_i->assertions & ASSERT_CHAR_CLASS_NEG) \
90 && tre_neg_char_classes_match(trans_i->neg_classes,(tre_cint_t)prev_c,\
91 tnfa->cflags & REG_ICASE)))
96 /* Returns 1 if `t1' wins `t2', 0 otherwise. */
98 tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions,
102 for (i = 0; i < num_tags; i++)
104 if (tag_directions[i] == TRE_TAG_MINIMIZE)
124 tre_neg_char_classes_match(tre_ctype_t *classes, tre_cint_t wc, int icase)
126 while (*classes != (tre_ctype_t)0)
127 if ((!icase && tre_isctype(wc, *classes))
128 || (icase && (tre_isctype(tre_toupper(wc), *classes)
129 || tre_isctype(tre_tolower(wc), *classes))))
130 return 1; /* Match. */
133 return 0; /* No match. */
137 /***********************************************************************
138 from tre-match-parallel.c
139 ***********************************************************************/
142 This algorithm searches for matches basically by reading characters
143 in the searched string one by one, starting at the beginning. All
144 matching paths in the TNFA are traversed in parallel. When two or
145 more paths reach the same state, exactly one is chosen according to
146 tag ordering rules; if returning submatches is not required it does
147 not matter which path is chosen.
149 The worst case time required for finding the leftmost and longest
150 match, or determining that there is no match, is always linearly
151 dependent on the length of the text being searched.
153 This algorithm cannot handle TNFAs with back referencing nodes.
154 See `tre-match-backtrack.c'.
158 tre_tnfa_transition_t *state;
169 tre_tnfa_run_parallel(const tre_tnfa_t *tnfa, const void *string,
170 int *match_tags, int eflags,
173 /* State variables required by GET_NEXT_WCHAR. */
174 tre_char_t prev_c = 0, next_c = 0;
175 const char *str_byte = string;
177 int pos_add_next = 1;
180 #endif /* TRE_MBSTATE */
181 int reg_notbol = eflags & REG_NOTBOL;
182 int reg_noteol = eflags & REG_NOTEOL;
183 int reg_newline = tnfa->cflags & REG_NEWLINE;
187 tre_tnfa_transition_t *trans_i;
188 tre_tnfa_reach_t *reach, *reach_next, *reach_i, *reach_next_i;
189 tre_reach_pos_t *reach_pos;
193 int match_eo = -1; /* end offset of match (-1 if no match found yet) */
195 int *tmp_tags = NULL;
199 memset(&mbstate, '\0', sizeof(mbstate));
200 #endif /* TRE_MBSTATE */
205 num_tags = tnfa->num_tags;
207 /* Allocate memory for temporary data required for matching. This needs to
208 be done for every matching operation to be thread safe. This allocates
209 everything in a single large block from the stack frame using alloca()
210 or with malloc() if alloca is unavailable. */
212 int tbytes, rbytes, pbytes, xbytes, total_bytes;
214 /* Compute the length of the block we need. */
215 tbytes = sizeof(*tmp_tags) * num_tags;
216 rbytes = sizeof(*reach_next) * (tnfa->num_states + 1);
217 pbytes = sizeof(*reach_pos) * tnfa->num_states;
218 xbytes = sizeof(int) * num_tags;
220 (sizeof(long) - 1) * 4 /* for alignment paddings */
221 + (rbytes + xbytes * tnfa->num_states) * 2 + tbytes + pbytes;
223 /* Allocate the memory. */
224 buf = xmalloc((unsigned)total_bytes);
227 memset(buf, 0, (size_t)total_bytes);
229 /* Get the various pointers within tmp_buf (properly aligned). */
230 tmp_tags = (void *)buf;
231 tmp_buf = buf + tbytes;
232 tmp_buf += ALIGN(tmp_buf, long);
233 reach_next = (void *)tmp_buf;
235 tmp_buf += ALIGN(tmp_buf, long);
236 reach = (void *)tmp_buf;
238 tmp_buf += ALIGN(tmp_buf, long);
239 reach_pos = (void *)tmp_buf;
241 tmp_buf += ALIGN(tmp_buf, long);
242 for (i = 0; i < tnfa->num_states; i++)
244 reach[i].tags = (void *)tmp_buf;
246 reach_next[i].tags = (void *)tmp_buf;
251 for (i = 0; i < tnfa->num_states; i++)
252 reach_pos[i].pos = -1;
257 reach_next_i = reach_next;
260 /* If no match found yet, add the initial states to `reach_next'. */
263 trans_i = tnfa->initial;
264 while (trans_i->state != NULL)
266 if (reach_pos[trans_i->state_id].pos < pos)
268 if (trans_i->assertions
269 && CHECK_ASSERTIONS(trans_i->assertions))
275 reach_next_i->state = trans_i->state;
276 for (i = 0; i < num_tags; i++)
277 reach_next_i->tags[i] = -1;
278 tag_i = trans_i->tags;
282 if (*tag_i < num_tags)
283 reach_next_i->tags[*tag_i] = pos;
286 if (reach_next_i->state == tnfa->final)
290 for (i = 0; i < num_tags; i++)
291 match_tags[i] = reach_next_i->tags[i];
293 reach_pos[trans_i->state_id].pos = pos;
294 reach_pos[trans_i->state_id].tags = &reach_next_i->tags;
299 reach_next_i->state = NULL;
303 if (num_tags == 0 || reach_next_i == reach_next)
304 /* We have found a match. */
308 /* Check for end of string. */
313 /* Swap `reach' and `reach_next'. */
316 reach_next = reach_i;
318 /* For each state in `reach', weed out states that don't fulfill the
319 minimal matching conditions. */
320 if (tnfa->num_minimals && new_match)
323 reach_next_i = reach_next;
324 for (reach_i = reach; reach_i->state; reach_i++)
327 for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2)
329 int end = tnfa->minimal_tags[i];
330 int start = tnfa->minimal_tags[i + 1];
336 else if (reach_i->tags[start] == match_tags[start]
337 && reach_i->tags[end] < match_tags[end])
345 reach_next_i->state = reach_i->state;
346 tmp_iptr = reach_next_i->tags;
347 reach_next_i->tags = reach_i->tags;
348 reach_i->tags = tmp_iptr;
352 reach_next_i->state = NULL;
354 /* Swap `reach' and `reach_next'. */
357 reach_next = reach_i;
360 /* For each state in `reach' see if there is a transition leaving with
361 the current input symbol to a state not yet in `reach_next', and
362 add the destination states to `reach_next'. */
363 reach_next_i = reach_next;
364 for (reach_i = reach; reach_i->state; reach_i++)
366 for (trans_i = reach_i->state; trans_i->state; trans_i++)
368 /* Does this transition match the input symbol? */
369 if (trans_i->code_min <= (tre_cint_t)prev_c &&
370 trans_i->code_max >= (tre_cint_t)prev_c)
372 if (trans_i->assertions
373 && (CHECK_ASSERTIONS(trans_i->assertions)
374 || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)))
379 /* Compute the tags after this transition. */
380 for (i = 0; i < num_tags; i++)
381 tmp_tags[i] = reach_i->tags[i];
382 tag_i = trans_i->tags;
386 if (*tag_i < num_tags)
387 tmp_tags[*tag_i] = pos;
391 if (reach_pos[trans_i->state_id].pos < pos)
393 /* Found an unvisited node. */
394 reach_next_i->state = trans_i->state;
395 tmp_iptr = reach_next_i->tags;
396 reach_next_i->tags = tmp_tags;
398 reach_pos[trans_i->state_id].pos = pos;
399 reach_pos[trans_i->state_id].tags = &reach_next_i->tags;
401 if (reach_next_i->state == tnfa->final
404 && reach_next_i->tags[0] <= match_tags[0])))
408 for (i = 0; i < num_tags; i++)
409 match_tags[i] = reach_next_i->tags[i];
416 assert(reach_pos[trans_i->state_id].pos == pos);
417 /* Another path has also reached this state. We choose
418 the winner by examining the tag values for both
420 if (tre_tag_order(num_tags, tnfa->tag_directions,
422 *reach_pos[trans_i->state_id].tags))
424 /* The new path wins. */
425 tmp_iptr = *reach_pos[trans_i->state_id].tags;
426 *reach_pos[trans_i->state_id].tags = tmp_tags;
427 if (trans_i->state == tnfa->final)
431 for (i = 0; i < num_tags; i++)
432 match_tags[i] = tmp_tags[i];
440 reach_next_i->state = NULL;
443 *match_end_ofs = match_eo;
444 ret = match_eo >= 0 ? REG_OK : REG_NOMATCH;
452 /***********************************************************************
453 from tre-match-backtrack.c
454 ***********************************************************************/
457 This matcher is for regexps that use back referencing. Regexp matching
458 with back referencing is an NP-complete problem on the number of back
459 references. The easiest way to match them is to use a backtracking
460 routine which basically goes through all possible paths in the TNFA
461 and chooses the one which results in the best (leftmost and longest)
462 match. This can be spectacularly expensive and may run out of stack
463 space, but there really is no better known generic algorithm. Quoting
464 Henry Spencer from comp.compilers:
465 <URL: http://compilers.iecc.com/comparch/article/93-03-102>
467 POSIX.2 REs require longest match, which is really exciting to
468 implement since the obsolete ("basic") variant also includes
469 \<digit>. I haven't found a better way of tackling this than doing
470 a preliminary match using a DFA (or simulation) on a modified RE
471 that just replicates subREs for \<digit>, and then doing a
472 backtracking match to determine whether the subRE matches were
473 right. This can be rather slow, but I console myself with the
474 thought that people who use \<digit> deserve very slow execution.
475 (Pun unintentional but very appropriate.)
481 const char *str_byte;
482 tre_tnfa_transition_t *state;
488 #endif /* TRE_MBSTATE */
489 } tre_backtrack_item_t;
491 typedef struct tre_backtrack_struct {
492 tre_backtrack_item_t item;
493 struct tre_backtrack_struct *prev;
494 struct tre_backtrack_struct *next;
498 #define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate)
499 #define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate
500 #else /* !TRE_MBSTATE */
501 #define BT_STACK_MBSTATE_IN
502 #define BT_STACK_MBSTATE_OUT
503 #endif /* !TRE_MBSTATE */
505 #define tre_bt_mem_new tre_mem_new
506 #define tre_bt_mem_alloc tre_mem_alloc
507 #define tre_bt_mem_destroy tre_mem_destroy
510 #define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \
517 s = tre_bt_mem_alloc(mem, sizeof(*s)); \
520 tre_bt_mem_destroy(mem); \
526 xfree(states_seen); \
531 s->item.tags = tre_bt_mem_alloc(mem, \
532 sizeof(*tags) * tnfa->num_tags); \
535 tre_bt_mem_destroy(mem); \
541 xfree(states_seen); \
548 stack = stack->next; \
549 stack->item.pos = (_pos); \
550 stack->item.str_byte = (_str_byte); \
551 stack->item.state = (_state); \
552 stack->item.state_id = (_state_id); \
553 stack->item.next_c = (_next_c); \
554 for (i = 0; i < tnfa->num_tags; i++) \
555 stack->item.tags[i] = (_tags)[i]; \
556 BT_STACK_MBSTATE_IN; \
560 #define BT_STACK_POP() \
564 assert(stack->prev); \
565 pos = stack->item.pos; \
566 str_byte = stack->item.str_byte; \
567 state = stack->item.state; \
568 next_c = stack->item.next_c; \
569 for (i = 0; i < tnfa->num_tags; i++) \
570 tags[i] = stack->item.tags[i]; \
571 BT_STACK_MBSTATE_OUT; \
572 stack = stack->prev; \
577 #define MIN(a, b) ((a) <= (b) ? (a) : (b))
580 tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string,
581 int *match_tags, int eflags, int *match_end_ofs)
583 /* State variables required by GET_NEXT_WCHAR. */
584 tre_char_t prev_c = 0, next_c = 0;
585 const char *str_byte = string;
587 int pos_add_next = 1;
590 #endif /* TRE_MBSTATE */
591 int reg_notbol = eflags & REG_NOTBOL;
592 int reg_noteol = eflags & REG_NOTEOL;
593 int reg_newline = tnfa->cflags & REG_NEWLINE;
595 /* These are used to remember the necessary values of the above
596 variables to return to the position where the current search
599 const char *str_byte_start;
602 mbstate_t mbstate_start;
603 #endif /* TRE_MBSTATE */
605 /* End offset of best match so far, or -1 if no match found yet. */
608 int *next_tags, *tags = NULL;
609 /* Current TNFA state. */
610 tre_tnfa_transition_t *state;
611 int *states_seen = NULL;
613 /* Memory allocator to for allocating the backtracking stack. */
614 tre_mem_t mem = tre_bt_mem_new();
616 /* The backtracking stack. */
617 tre_backtrack_t stack;
619 tre_tnfa_transition_t *trans_i;
620 regmatch_t *pmatch = NULL;
624 memset(&mbstate, '\0', sizeof(mbstate));
625 #endif /* TRE_MBSTATE */
629 stack = tre_bt_mem_alloc(mem, sizeof(*stack));
640 tags = xmalloc(sizeof(*tags) * tnfa->num_tags);
647 if (tnfa->num_submatches)
649 pmatch = xmalloc(sizeof(*pmatch) * tnfa->num_submatches);
656 if (tnfa->num_states)
658 states_seen = xmalloc(sizeof(*states_seen) * tnfa->num_states);
669 for (i = 0; i < tnfa->num_tags; i++)
675 for (i = 0; i < tnfa->num_states; i++)
683 next_c_start = next_c;
684 str_byte_start = str_byte;
686 mbstate_start = mbstate;
687 #endif /* TRE_MBSTATE */
689 /* Handle initial states. */
691 for (trans_i = tnfa->initial; trans_i->state; trans_i++)
693 if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions))
699 /* Start from this state. */
700 state = trans_i->state;
701 next_tags = trans_i->tags;
705 /* Backtrack to this state. */
706 BT_STACK_PUSH(pos, str_byte, 0, trans_i->state,
707 trans_i->state_id, next_c, tags, mbstate);
709 int *tmp = trans_i->tags;
712 stack->item.tags[*tmp++] = pos;
718 for (; *next_tags >= 0; next_tags++)
719 tags[*next_tags] = pos;
727 tre_tnfa_transition_t *next_state;
730 if (state == tnfa->final)
735 && tre_tag_order(tnfa->num_tags, tnfa->tag_directions,
739 /* This match wins the previous match. */
742 for (i = 0; i < tnfa->num_tags; i++)
743 match_tags[i] = tags[i];
745 /* Our TNFAs never have transitions leaving from the final state,
746 so we jump right to backtracking. */
750 /* Go to the next character in the input string. */
753 if (trans_i->state && trans_i->assertions & ASSERT_BACKREF)
755 /* This is a back reference state. All transitions leaving from
756 this state have the same back reference "assertion". Instead
757 of reading the next character, we match the back reference. */
758 int so, eo, bt = trans_i->u.backref;
762 /* Get the substring we need to match against. Remember to
763 turn off REG_NOSUB temporarily. */
764 tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB,
766 so = pmatch[bt].rm_so;
767 eo = pmatch[bt].rm_eo;
770 result = strncmp((const char*)string + so, str_byte - 1,
775 /* Back reference matched. Check for infinite loop. */
778 if (empty_br_match && states_seen[trans_i->state_id])
783 states_seen[trans_i->state_id] = empty_br_match;
785 /* Advance in input string and resync `prev_c', `next_c'
787 str_byte += bt_len - 1;
798 /* Check for end of string. */
802 /* Read the next character. */
807 for (trans_i = state; trans_i->state; trans_i++)
809 if (trans_i->code_min <= (tre_cint_t)prev_c
810 && trans_i->code_max >= (tre_cint_t)prev_c)
812 if (trans_i->assertions
813 && (CHECK_ASSERTIONS(trans_i->assertions)
814 || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)))
819 if (next_state == NULL)
821 /* First matching transition. */
822 next_state = trans_i->state;
823 next_tags = trans_i->tags;
827 /* Second matching transition. We may need to backtrack here
828 to take this transition instead of the first one, so we
829 push this transition in the backtracking stack so we can
830 jump back here if needed. */
831 BT_STACK_PUSH(pos, str_byte, 0, trans_i->state,
832 trans_i->state_id, next_c, tags, mbstate);
835 for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++)
836 stack->item.tags[*tmp] = pos;
838 #if 0 /* XXX - it's important not to look at all transitions here to keep
846 if (next_state != NULL)
848 /* Matching transitions were found. Take the first one. */
851 /* Update the tag values. */
853 while (*next_tags >= 0)
854 tags[*next_tags++] = pos;
859 /* A matching transition was not found. Try to backtrack. */
862 if (stack->item.state->assertions & ASSERT_BACKREF)
864 states_seen[stack->item.state_id] = 0;
869 else if (match_eo < 0)
871 /* Try starting from a later position in the input string. */
872 /* Check for end of string. */
877 next_c = next_c_start;
879 mbstate = mbstate_start;
880 #endif /* TRE_MBSTATE */
881 str_byte = str_byte_start;
891 ret = match_eo >= 0 ? REG_OK : REG_NOMATCH;
892 *match_end_ofs = match_eo;
895 tre_bt_mem_destroy(mem);
896 #ifndef TRE_USE_ALLOCA
903 #endif /* !TRE_USE_ALLOCA */
908 /***********************************************************************
910 ***********************************************************************/
912 /* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match
915 tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
916 const tre_tnfa_t *tnfa, int *tags, int match_eo)
918 tre_submatch_data_t *submatch_data;
923 if (match_eo >= 0 && !(cflags & REG_NOSUB))
925 /* Construct submatch offsets from the tags. */
926 submatch_data = tnfa->submatch_data;
927 while (i < tnfa->num_submatches && i < nmatch)
929 if (submatch_data[i].so_tag == tnfa->end_tag)
930 pmatch[i].rm_so = match_eo;
932 pmatch[i].rm_so = tags[submatch_data[i].so_tag];
934 if (submatch_data[i].eo_tag == tnfa->end_tag)
935 pmatch[i].rm_eo = match_eo;
937 pmatch[i].rm_eo = tags[submatch_data[i].eo_tag];
939 /* If either of the endpoints were not used, this submatch
940 was not part of the match. */
941 if (pmatch[i].rm_so == -1 || pmatch[i].rm_eo == -1)
942 pmatch[i].rm_so = pmatch[i].rm_eo = -1;
946 /* Reset all submatches that are not within all of their parent
949 while (i < tnfa->num_submatches && i < nmatch)
951 if (pmatch[i].rm_eo == -1)
952 assert(pmatch[i].rm_so == -1);
953 assert(pmatch[i].rm_so <= pmatch[i].rm_eo);
955 parents = submatch_data[i].parents;
957 for (j = 0; parents[j] >= 0; j++)
959 if (pmatch[i].rm_so < pmatch[parents[j]].rm_so
960 || pmatch[i].rm_eo > pmatch[parents[j]].rm_eo)
961 pmatch[i].rm_so = pmatch[i].rm_eo = -1;
969 pmatch[i].rm_so = -1;
970 pmatch[i].rm_eo = -1;
977 Wrapper functions for POSIX compatible regexp matching.
981 regexec(const regex_t *restrict preg, const char *restrict string,
982 size_t nmatch, regmatch_t pmatch[restrict], int eflags)
984 tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD;
985 reg_errcode_t status;
986 int *tags = NULL, eo;
987 if (tnfa->cflags & REG_NOSUB) nmatch = 0;
988 if (tnfa->num_tags > 0 && nmatch > 0)
990 tags = xmalloc(sizeof(*tags) * tnfa->num_tags);
995 /* Dispatch to the appropriate matcher. */
996 if (tnfa->have_backrefs)
998 /* The regex has back references, use the backtracking matcher. */
999 status = tre_tnfa_run_backtrack(tnfa, string, tags, eflags, &eo);
1003 /* Exact matching, no back references, use the parallel matcher. */
1004 status = tre_tnfa_run_parallel(tnfa, string, tags, eflags, &eo);
1007 if (status == REG_OK)
1008 /* A match was found, so fill the submatch registers. */
1009 tre_fill_pmatch(nmatch, pmatch, tnfa->cflags, tnfa, tags, eo);