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) return REG_NOMATCH; \
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;
186 tre_tnfa_transition_t *trans_i;
187 tre_tnfa_reach_t *reach, *reach_next, *reach_i, *reach_next_i;
188 tre_reach_pos_t *reach_pos;
192 int match_eo = -1; /* end offset of match (-1 if no match found yet) */
194 int *tmp_tags = NULL;
198 memset(&mbstate, '\0', sizeof(mbstate));
199 #endif /* TRE_MBSTATE */
204 num_tags = tnfa->num_tags;
206 /* Allocate memory for temporary data required for matching. This needs to
207 be done for every matching operation to be thread safe. This allocates
208 everything in a single large block from the stack frame using alloca()
209 or with malloc() if alloca is unavailable. */
211 int tbytes, rbytes, pbytes, xbytes, total_bytes;
213 /* Compute the length of the block we need. */
214 tbytes = sizeof(*tmp_tags) * num_tags;
215 rbytes = sizeof(*reach_next) * (tnfa->num_states + 1);
216 pbytes = sizeof(*reach_pos) * tnfa->num_states;
217 xbytes = sizeof(int) * num_tags;
219 (sizeof(long) - 1) * 4 /* for alignment paddings */
220 + (rbytes + xbytes * tnfa->num_states) * 2 + tbytes + pbytes;
222 /* Allocate the memory. */
223 buf = xmalloc((unsigned)total_bytes);
226 memset(buf, 0, (size_t)total_bytes);
228 /* Get the various pointers within tmp_buf (properly aligned). */
229 tmp_tags = (void *)buf;
230 tmp_buf = buf + tbytes;
231 tmp_buf += ALIGN(tmp_buf, long);
232 reach_next = (void *)tmp_buf;
234 tmp_buf += ALIGN(tmp_buf, long);
235 reach = (void *)tmp_buf;
237 tmp_buf += ALIGN(tmp_buf, long);
238 reach_pos = (void *)tmp_buf;
240 tmp_buf += ALIGN(tmp_buf, long);
241 for (i = 0; i < tnfa->num_states; i++)
243 reach[i].tags = (void *)tmp_buf;
245 reach_next[i].tags = (void *)tmp_buf;
250 for (i = 0; i < tnfa->num_states; i++)
251 reach_pos[i].pos = -1;
256 reach_next_i = reach_next;
259 /* If no match found yet, add the initial states to `reach_next'. */
262 trans_i = tnfa->initial;
263 while (trans_i->state != NULL)
265 if (reach_pos[trans_i->state_id].pos < pos)
267 if (trans_i->assertions
268 && CHECK_ASSERTIONS(trans_i->assertions))
274 reach_next_i->state = trans_i->state;
275 for (i = 0; i < num_tags; i++)
276 reach_next_i->tags[i] = -1;
277 tag_i = trans_i->tags;
281 if (*tag_i < num_tags)
282 reach_next_i->tags[*tag_i] = pos;
285 if (reach_next_i->state == tnfa->final)
289 for (i = 0; i < num_tags; i++)
290 match_tags[i] = reach_next_i->tags[i];
292 reach_pos[trans_i->state_id].pos = pos;
293 reach_pos[trans_i->state_id].tags = &reach_next_i->tags;
298 reach_next_i->state = NULL;
302 if (num_tags == 0 || reach_next_i == reach_next)
303 /* We have found a match. */
307 /* Check for end of string. */
312 /* Swap `reach' and `reach_next'. */
315 reach_next = reach_i;
317 /* For each state in `reach', weed out states that don't fulfill the
318 minimal matching conditions. */
319 if (tnfa->num_minimals && new_match)
322 reach_next_i = reach_next;
323 for (reach_i = reach; reach_i->state; reach_i++)
326 for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2)
328 int end = tnfa->minimal_tags[i];
329 int start = tnfa->minimal_tags[i + 1];
335 else if (reach_i->tags[start] == match_tags[start]
336 && reach_i->tags[end] < match_tags[end])
344 reach_next_i->state = reach_i->state;
345 tmp_iptr = reach_next_i->tags;
346 reach_next_i->tags = reach_i->tags;
347 reach_i->tags = tmp_iptr;
351 reach_next_i->state = NULL;
353 /* Swap `reach' and `reach_next'. */
356 reach_next = reach_i;
359 /* For each state in `reach' see if there is a transition leaving with
360 the current input symbol to a state not yet in `reach_next', and
361 add the destination states to `reach_next'. */
362 reach_next_i = reach_next;
363 for (reach_i = reach; reach_i->state; reach_i++)
365 for (trans_i = reach_i->state; trans_i->state; trans_i++)
367 /* Does this transition match the input symbol? */
368 if (trans_i->code_min <= (tre_cint_t)prev_c &&
369 trans_i->code_max >= (tre_cint_t)prev_c)
371 if (trans_i->assertions
372 && (CHECK_ASSERTIONS(trans_i->assertions)
373 || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)))
378 /* Compute the tags after this transition. */
379 for (i = 0; i < num_tags; i++)
380 tmp_tags[i] = reach_i->tags[i];
381 tag_i = trans_i->tags;
385 if (*tag_i < num_tags)
386 tmp_tags[*tag_i] = pos;
390 if (reach_pos[trans_i->state_id].pos < pos)
392 /* Found an unvisited node. */
393 reach_next_i->state = trans_i->state;
394 tmp_iptr = reach_next_i->tags;
395 reach_next_i->tags = tmp_tags;
397 reach_pos[trans_i->state_id].pos = pos;
398 reach_pos[trans_i->state_id].tags = &reach_next_i->tags;
400 if (reach_next_i->state == tnfa->final
403 && reach_next_i->tags[0] <= match_tags[0])))
407 for (i = 0; i < num_tags; i++)
408 match_tags[i] = reach_next_i->tags[i];
415 assert(reach_pos[trans_i->state_id].pos == pos);
416 /* Another path has also reached this state. We choose
417 the winner by examining the tag values for both
419 if (tre_tag_order(num_tags, tnfa->tag_directions,
421 *reach_pos[trans_i->state_id].tags))
423 /* The new path wins. */
424 tmp_iptr = *reach_pos[trans_i->state_id].tags;
425 *reach_pos[trans_i->state_id].tags = tmp_tags;
426 if (trans_i->state == tnfa->final)
430 for (i = 0; i < num_tags; i++)
431 match_tags[i] = tmp_tags[i];
439 reach_next_i->state = NULL;
445 *match_end_ofs = match_eo;
446 return match_eo >= 0 ? REG_OK : REG_NOMATCH;
451 /***********************************************************************
452 from tre-match-backtrack.c
453 ***********************************************************************/
456 This matcher is for regexps that use back referencing. Regexp matching
457 with back referencing is an NP-complete problem on the number of back
458 references. The easiest way to match them is to use a backtracking
459 routine which basically goes through all possible paths in the TNFA
460 and chooses the one which results in the best (leftmost and longest)
461 match. This can be spectacularly expensive and may run out of stack
462 space, but there really is no better known generic algorithm. Quoting
463 Henry Spencer from comp.compilers:
464 <URL: http://compilers.iecc.com/comparch/article/93-03-102>
466 POSIX.2 REs require longest match, which is really exciting to
467 implement since the obsolete ("basic") variant also includes
468 \<digit>. I haven't found a better way of tackling this than doing
469 a preliminary match using a DFA (or simulation) on a modified RE
470 that just replicates subREs for \<digit>, and then doing a
471 backtracking match to determine whether the subRE matches were
472 right. This can be rather slow, but I console myself with the
473 thought that people who use \<digit> deserve very slow execution.
474 (Pun unintentional but very appropriate.)
480 const char *str_byte;
481 tre_tnfa_transition_t *state;
487 #endif /* TRE_MBSTATE */
488 } tre_backtrack_item_t;
490 typedef struct tre_backtrack_struct {
491 tre_backtrack_item_t item;
492 struct tre_backtrack_struct *prev;
493 struct tre_backtrack_struct *next;
497 #define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate)
498 #define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate
499 #else /* !TRE_MBSTATE */
500 #define BT_STACK_MBSTATE_IN
501 #define BT_STACK_MBSTATE_OUT
502 #endif /* !TRE_MBSTATE */
504 #define tre_bt_mem_new tre_mem_new
505 #define tre_bt_mem_alloc tre_mem_alloc
506 #define tre_bt_mem_destroy tre_mem_destroy
509 #define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \
516 s = tre_bt_mem_alloc(mem, sizeof(*s)); \
519 tre_bt_mem_destroy(mem); \
525 xfree(states_seen); \
530 s->item.tags = tre_bt_mem_alloc(mem, \
531 sizeof(*tags) * tnfa->num_tags); \
534 tre_bt_mem_destroy(mem); \
540 xfree(states_seen); \
547 stack = stack->next; \
548 stack->item.pos = (_pos); \
549 stack->item.str_byte = (_str_byte); \
550 stack->item.state = (_state); \
551 stack->item.state_id = (_state_id); \
552 stack->item.next_c = (_next_c); \
553 for (i = 0; i < tnfa->num_tags; i++) \
554 stack->item.tags[i] = (_tags)[i]; \
555 BT_STACK_MBSTATE_IN; \
559 #define BT_STACK_POP() \
563 assert(stack->prev); \
564 pos = stack->item.pos; \
565 str_byte = stack->item.str_byte; \
566 state = stack->item.state; \
567 next_c = stack->item.next_c; \
568 for (i = 0; i < tnfa->num_tags; i++) \
569 tags[i] = stack->item.tags[i]; \
570 BT_STACK_MBSTATE_OUT; \
571 stack = stack->prev; \
576 #define MIN(a, b) ((a) <= (b) ? (a) : (b))
579 tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string,
580 int *match_tags, int eflags, int *match_end_ofs)
582 /* State variables required by GET_NEXT_WCHAR. */
583 tre_char_t prev_c = 0, next_c = 0;
584 const char *str_byte = string;
586 int pos_add_next = 1;
589 #endif /* TRE_MBSTATE */
590 int reg_notbol = eflags & REG_NOTBOL;
591 int reg_noteol = eflags & REG_NOTEOL;
592 int reg_newline = tnfa->cflags & REG_NEWLINE;
594 /* These are used to remember the necessary values of the above
595 variables to return to the position where the current search
598 const char *str_byte_start;
601 mbstate_t mbstate_start;
602 #endif /* TRE_MBSTATE */
604 /* End offset of best match so far, or -1 if no match found yet. */
607 int *next_tags, *tags = NULL;
608 /* Current TNFA state. */
609 tre_tnfa_transition_t *state;
610 int *states_seen = NULL;
612 /* Memory allocator to for allocating the backtracking stack. */
613 tre_mem_t mem = tre_bt_mem_new();
615 /* The backtracking stack. */
616 tre_backtrack_t stack;
618 tre_tnfa_transition_t *trans_i;
619 regmatch_t *pmatch = NULL;
623 memset(&mbstate, '\0', sizeof(mbstate));
624 #endif /* TRE_MBSTATE */
628 stack = tre_bt_mem_alloc(mem, sizeof(*stack));
639 tags = xmalloc(sizeof(*tags) * tnfa->num_tags);
646 if (tnfa->num_submatches)
648 pmatch = xmalloc(sizeof(*pmatch) * tnfa->num_submatches);
655 if (tnfa->num_states)
657 states_seen = xmalloc(sizeof(*states_seen) * tnfa->num_states);
668 for (i = 0; i < tnfa->num_tags; i++)
674 for (i = 0; i < tnfa->num_states; i++)
682 next_c_start = next_c;
683 str_byte_start = str_byte;
685 mbstate_start = mbstate;
686 #endif /* TRE_MBSTATE */
688 /* Handle initial states. */
690 for (trans_i = tnfa->initial; trans_i->state; trans_i++)
692 if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions))
698 /* Start from this state. */
699 state = trans_i->state;
700 next_tags = trans_i->tags;
704 /* Backtrack to this state. */
705 BT_STACK_PUSH(pos, str_byte, 0, trans_i->state,
706 trans_i->state_id, next_c, tags, mbstate);
708 int *tmp = trans_i->tags;
711 stack->item.tags[*tmp++] = pos;
717 for (; *next_tags >= 0; next_tags++)
718 tags[*next_tags] = pos;
726 tre_tnfa_transition_t *next_state;
729 if (state == tnfa->final)
734 && tre_tag_order(tnfa->num_tags, tnfa->tag_directions,
738 /* This match wins the previous match. */
741 for (i = 0; i < tnfa->num_tags; i++)
742 match_tags[i] = tags[i];
744 /* Our TNFAs never have transitions leaving from the final state,
745 so we jump right to backtracking. */
749 /* Go to the next character in the input string. */
752 if (trans_i->state && trans_i->assertions & ASSERT_BACKREF)
754 /* This is a back reference state. All transitions leaving from
755 this state have the same back reference "assertion". Instead
756 of reading the next character, we match the back reference. */
757 int so, eo, bt = trans_i->u.backref;
761 /* Get the substring we need to match against. Remember to
762 turn off REG_NOSUB temporarily. */
763 tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB,
765 so = pmatch[bt].rm_so;
766 eo = pmatch[bt].rm_eo;
769 result = strncmp((const char*)string + so, str_byte - 1,
774 /* Back reference matched. Check for infinite loop. */
777 if (empty_br_match && states_seen[trans_i->state_id])
782 states_seen[trans_i->state_id] = empty_br_match;
784 /* Advance in input string and resync `prev_c', `next_c'
786 str_byte += bt_len - 1;
797 /* Check for end of string. */
801 /* Read the next character. */
806 for (trans_i = state; trans_i->state; trans_i++)
808 if (trans_i->code_min <= (tre_cint_t)prev_c
809 && trans_i->code_max >= (tre_cint_t)prev_c)
811 if (trans_i->assertions
812 && (CHECK_ASSERTIONS(trans_i->assertions)
813 || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)))
818 if (next_state == NULL)
820 /* First matching transition. */
821 next_state = trans_i->state;
822 next_tags = trans_i->tags;
826 /* Second matching transition. We may need to backtrack here
827 to take this transition instead of the first one, so we
828 push this transition in the backtracking stack so we can
829 jump back here if needed. */
830 BT_STACK_PUSH(pos, str_byte, 0, trans_i->state,
831 trans_i->state_id, next_c, tags, mbstate);
834 for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++)
835 stack->item.tags[*tmp] = pos;
837 #if 0 /* XXX - it's important not to look at all transitions here to keep
845 if (next_state != NULL)
847 /* Matching transitions were found. Take the first one. */
850 /* Update the tag values. */
852 while (*next_tags >= 0)
853 tags[*next_tags++] = pos;
858 /* A matching transition was not found. Try to backtrack. */
861 if (stack->item.state->assertions & ASSERT_BACKREF)
863 states_seen[stack->item.state_id] = 0;
868 else if (match_eo < 0)
870 /* Try starting from a later position in the input string. */
871 /* Check for end of string. */
876 next_c = next_c_start;
878 mbstate = mbstate_start;
879 #endif /* TRE_MBSTATE */
880 str_byte = str_byte_start;
890 ret = match_eo >= 0 ? REG_OK : REG_NOMATCH;
891 *match_end_ofs = match_eo;
894 tre_bt_mem_destroy(mem);
895 #ifndef TRE_USE_ALLOCA
902 #endif /* !TRE_USE_ALLOCA */
907 /***********************************************************************
909 ***********************************************************************/
911 /* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match
914 tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
915 const tre_tnfa_t *tnfa, int *tags, int match_eo)
917 tre_submatch_data_t *submatch_data;
922 if (match_eo >= 0 && !(cflags & REG_NOSUB))
924 /* Construct submatch offsets from the tags. */
925 submatch_data = tnfa->submatch_data;
926 while (i < tnfa->num_submatches && i < nmatch)
928 if (submatch_data[i].so_tag == tnfa->end_tag)
929 pmatch[i].rm_so = match_eo;
931 pmatch[i].rm_so = tags[submatch_data[i].so_tag];
933 if (submatch_data[i].eo_tag == tnfa->end_tag)
934 pmatch[i].rm_eo = match_eo;
936 pmatch[i].rm_eo = tags[submatch_data[i].eo_tag];
938 /* If either of the endpoints were not used, this submatch
939 was not part of the match. */
940 if (pmatch[i].rm_so == -1 || pmatch[i].rm_eo == -1)
941 pmatch[i].rm_so = pmatch[i].rm_eo = -1;
945 /* Reset all submatches that are not within all of their parent
948 while (i < tnfa->num_submatches && i < nmatch)
950 if (pmatch[i].rm_eo == -1)
951 assert(pmatch[i].rm_so == -1);
952 assert(pmatch[i].rm_so <= pmatch[i].rm_eo);
954 parents = submatch_data[i].parents;
956 for (j = 0; parents[j] >= 0; j++)
958 if (pmatch[i].rm_so < pmatch[parents[j]].rm_so
959 || pmatch[i].rm_eo > pmatch[parents[j]].rm_eo)
960 pmatch[i].rm_so = pmatch[i].rm_eo = -1;
968 pmatch[i].rm_so = -1;
969 pmatch[i].rm_eo = -1;
976 Wrapper functions for POSIX compatible regexp matching.
980 regexec(const regex_t *preg, const char *string,
981 size_t nmatch, regmatch_t pmatch[], int eflags)
983 tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD;
984 reg_errcode_t status;
985 int *tags = NULL, eo;
986 if (tnfa->num_tags > 0 && nmatch > 0)
988 tags = xmalloc(sizeof(*tags) * tnfa->num_tags);
993 /* Dispatch to the appropriate matcher. */
994 if (tnfa->have_backrefs)
996 /* The regex has back references, use the backtracking matcher. */
997 status = tre_tnfa_run_backtrack(tnfa, string, tags, eflags, &eo);
1001 /* Exact matching, no back references, use the parallel matcher. */
1002 status = tre_tnfa_run_parallel(tnfa, string, tags, eflags, &eo);
1005 if (status == REG_OK)
1006 /* A match was found, so fill the submatch registers. */
1007 tre_fill_pmatch(nmatch, pmatch, tnfa->cflags, tnfa, tags, eo);