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.
46 tre_fill_pmatch(size_t nmatch
, regmatch_t pmatch
[], int cflags
,
47 const tre_tnfa_t
*tnfa
, regoff_t
*tags
, regoff_t match_eo
);
49 /***********************************************************************
50 from tre-match-utils.h
51 ***********************************************************************/
53 #define GET_NEXT_WCHAR() do { \
54 prev_c = next_c; pos += pos_add_next; \
55 if ((pos_add_next = mbtowc(&next_c, str_byte, MB_LEN_MAX)) <= 0) { \
56 if (pos_add_next < 0) { ret = REG_NOMATCH; goto error_exit; } \
57 else pos_add_next++; \
59 str_byte += pos_add_next; \
62 #define IS_WORD_CHAR(c) ((c) == L'_' || tre_isalnum(c))
64 #define CHECK_ASSERTIONS(assertions) \
65 (((assertions & ASSERT_AT_BOL) \
66 && (pos > 0 || reg_notbol) \
67 && (prev_c != L'\n' || !reg_newline)) \
68 || ((assertions & ASSERT_AT_EOL) \
69 && (next_c != L'\0' || reg_noteol) \
70 && (next_c != L'\n' || !reg_newline)) \
71 || ((assertions & ASSERT_AT_BOW) \
72 && (IS_WORD_CHAR(prev_c) || !IS_WORD_CHAR(next_c))) \
73 || ((assertions & ASSERT_AT_EOW) \
74 && (!IS_WORD_CHAR(prev_c) || IS_WORD_CHAR(next_c))) \
75 || ((assertions & ASSERT_AT_WB) \
76 && (pos != 0 && next_c != L'\0' \
77 && IS_WORD_CHAR(prev_c) == IS_WORD_CHAR(next_c))) \
78 || ((assertions & ASSERT_AT_WB_NEG) \
79 && (pos == 0 || next_c == L'\0' \
80 || IS_WORD_CHAR(prev_c) != IS_WORD_CHAR(next_c))))
82 #define CHECK_CHAR_CLASSES(trans_i, tnfa, eflags) \
83 (((trans_i->assertions & ASSERT_CHAR_CLASS) \
84 && !(tnfa->cflags & REG_ICASE) \
85 && !tre_isctype((tre_cint_t)prev_c, trans_i->u.class)) \
86 || ((trans_i->assertions & ASSERT_CHAR_CLASS) \
87 && (tnfa->cflags & REG_ICASE) \
88 && !tre_isctype(tre_tolower((tre_cint_t)prev_c),trans_i->u.class) \
89 && !tre_isctype(tre_toupper((tre_cint_t)prev_c),trans_i->u.class)) \
90 || ((trans_i->assertions & ASSERT_CHAR_CLASS_NEG) \
91 && tre_neg_char_classes_match(trans_i->neg_classes,(tre_cint_t)prev_c,\
92 tnfa->cflags & REG_ICASE)))
97 /* Returns 1 if `t1' wins `t2', 0 otherwise. */
99 tre_tag_order(int num_tags
, tre_tag_direction_t
*tag_directions
,
100 regoff_t
*t1
, regoff_t
*t2
)
103 for (i
= 0; i
< num_tags
; i
++)
105 if (tag_directions
[i
] == TRE_TAG_MINIMIZE
)
125 tre_neg_char_classes_match(tre_ctype_t
*classes
, tre_cint_t wc
, int icase
)
127 while (*classes
!= (tre_ctype_t
)0)
128 if ((!icase
&& tre_isctype(wc
, *classes
))
129 || (icase
&& (tre_isctype(tre_toupper(wc
), *classes
)
130 || tre_isctype(tre_tolower(wc
), *classes
))))
131 return 1; /* Match. */
134 return 0; /* No match. */
138 /***********************************************************************
139 from tre-match-parallel.c
140 ***********************************************************************/
143 This algorithm searches for matches basically by reading characters
144 in the searched string one by one, starting at the beginning. All
145 matching paths in the TNFA are traversed in parallel. When two or
146 more paths reach the same state, exactly one is chosen according to
147 tag ordering rules; if returning submatches is not required it does
148 not matter which path is chosen.
150 The worst case time required for finding the leftmost and longest
151 match, or determining that there is no match, is always linearly
152 dependent on the length of the text being searched.
154 This algorithm cannot handle TNFAs with back referencing nodes.
155 See `tre-match-backtrack.c'.
159 tre_tnfa_transition_t
*state
;
170 tre_tnfa_run_parallel(const tre_tnfa_t
*tnfa
, const void *string
,
171 regoff_t
*match_tags
, int eflags
,
172 regoff_t
*match_end_ofs
)
174 /* State variables required by GET_NEXT_WCHAR. */
175 tre_char_t prev_c
= 0, next_c
= 0;
176 const char *str_byte
= string
;
178 regoff_t pos_add_next
= 1;
181 #endif /* TRE_MBSTATE */
182 int reg_notbol
= eflags
& REG_NOTBOL
;
183 int reg_noteol
= eflags
& REG_NOTEOL
;
184 int reg_newline
= tnfa
->cflags
& REG_NEWLINE
;
188 tre_tnfa_transition_t
*trans_i
;
189 tre_tnfa_reach_t
*reach
, *reach_next
, *reach_i
, *reach_next_i
;
190 tre_reach_pos_t
*reach_pos
;
194 regoff_t match_eo
= -1; /* end offset of match (-1 if no match found yet) */
196 regoff_t
*tmp_tags
= NULL
;
200 memset(&mbstate
, '\0', sizeof(mbstate
));
201 #endif /* TRE_MBSTATE */
206 num_tags
= tnfa
->num_tags
;
208 /* Allocate memory for temporary data required for matching. This needs to
209 be done for every matching operation to be thread safe. This allocates
210 everything in a single large block with calloc(). */
212 size_t tbytes
, rbytes
, pbytes
, xbytes
, total_bytes
;
215 /* Ensure that tbytes and xbytes*num_states cannot overflow, and that
216 * they don't contribute more than 1/8 of SIZE_MAX to total_bytes. */
217 if (num_tags
> SIZE_MAX
/(8 * sizeof(regoff_t
) * tnfa
->num_states
))
220 /* Likewise check rbytes. */
221 if (tnfa
->num_states
+1 > SIZE_MAX
/(8 * sizeof(*reach_next
)))
224 /* Likewise check pbytes. */
225 if (tnfa
->num_states
> SIZE_MAX
/(8 * sizeof(*reach_pos
)))
228 /* Compute the length of the block we need. */
229 tbytes
= sizeof(*tmp_tags
) * num_tags
;
230 rbytes
= sizeof(*reach_next
) * (tnfa
->num_states
+ 1);
231 pbytes
= sizeof(*reach_pos
) * tnfa
->num_states
;
232 xbytes
= sizeof(regoff_t
) * num_tags
;
234 (sizeof(long) - 1) * 4 /* for alignment paddings */
235 + (rbytes
+ xbytes
* tnfa
->num_states
) * 2 + tbytes
+ pbytes
;
237 /* Allocate the memory. */
238 buf
= calloc(total_bytes
, 1);
242 /* Get the various pointers within tmp_buf (properly aligned). */
243 tmp_tags
= (void *)buf
;
244 tmp_buf
= buf
+ tbytes
;
245 tmp_buf
+= ALIGN(tmp_buf
, long);
246 reach_next
= (void *)tmp_buf
;
248 tmp_buf
+= ALIGN(tmp_buf
, long);
249 reach
= (void *)tmp_buf
;
251 tmp_buf
+= ALIGN(tmp_buf
, long);
252 reach_pos
= (void *)tmp_buf
;
254 tmp_buf
+= ALIGN(tmp_buf
, long);
255 for (i
= 0; i
< tnfa
->num_states
; i
++)
257 reach
[i
].tags
= (void *)tmp_buf
;
259 reach_next
[i
].tags
= (void *)tmp_buf
;
264 for (i
= 0; i
< tnfa
->num_states
; i
++)
265 reach_pos
[i
].pos
= -1;
270 reach_next_i
= reach_next
;
273 /* If no match found yet, add the initial states to `reach_next'. */
276 trans_i
= tnfa
->initial
;
277 while (trans_i
->state
!= NULL
)
279 if (reach_pos
[trans_i
->state_id
].pos
< pos
)
281 if (trans_i
->assertions
282 && CHECK_ASSERTIONS(trans_i
->assertions
))
288 reach_next_i
->state
= trans_i
->state
;
289 for (i
= 0; i
< num_tags
; i
++)
290 reach_next_i
->tags
[i
] = -1;
291 tag_i
= trans_i
->tags
;
295 if (*tag_i
< num_tags
)
296 reach_next_i
->tags
[*tag_i
] = pos
;
299 if (reach_next_i
->state
== tnfa
->final
)
303 for (i
= 0; i
< num_tags
; i
++)
304 match_tags
[i
] = reach_next_i
->tags
[i
];
306 reach_pos
[trans_i
->state_id
].pos
= pos
;
307 reach_pos
[trans_i
->state_id
].tags
= &reach_next_i
->tags
;
312 reach_next_i
->state
= NULL
;
316 if (num_tags
== 0 || reach_next_i
== reach_next
)
317 /* We have found a match. */
321 /* Check for end of string. */
326 /* Swap `reach' and `reach_next'. */
329 reach_next
= reach_i
;
331 /* For each state in `reach', weed out states that don't fulfill the
332 minimal matching conditions. */
333 if (tnfa
->num_minimals
&& new_match
)
336 reach_next_i
= reach_next
;
337 for (reach_i
= reach
; reach_i
->state
; reach_i
++)
340 for (i
= 0; tnfa
->minimal_tags
[i
] >= 0; i
+= 2)
342 int end
= tnfa
->minimal_tags
[i
];
343 int start
= tnfa
->minimal_tags
[i
+ 1];
349 else if (reach_i
->tags
[start
] == match_tags
[start
]
350 && reach_i
->tags
[end
] < match_tags
[end
])
358 reach_next_i
->state
= reach_i
->state
;
359 tmp_iptr
= reach_next_i
->tags
;
360 reach_next_i
->tags
= reach_i
->tags
;
361 reach_i
->tags
= tmp_iptr
;
365 reach_next_i
->state
= NULL
;
367 /* Swap `reach' and `reach_next'. */
370 reach_next
= reach_i
;
373 /* For each state in `reach' see if there is a transition leaving with
374 the current input symbol to a state not yet in `reach_next', and
375 add the destination states to `reach_next'. */
376 reach_next_i
= reach_next
;
377 for (reach_i
= reach
; reach_i
->state
; reach_i
++)
379 for (trans_i
= reach_i
->state
; trans_i
->state
; trans_i
++)
381 /* Does this transition match the input symbol? */
382 if (trans_i
->code_min
<= (tre_cint_t
)prev_c
&&
383 trans_i
->code_max
>= (tre_cint_t
)prev_c
)
385 if (trans_i
->assertions
386 && (CHECK_ASSERTIONS(trans_i
->assertions
)
387 || CHECK_CHAR_CLASSES(trans_i
, tnfa
, eflags
)))
392 /* Compute the tags after this transition. */
393 for (i
= 0; i
< num_tags
; i
++)
394 tmp_tags
[i
] = reach_i
->tags
[i
];
395 tag_i
= trans_i
->tags
;
399 if (*tag_i
< num_tags
)
400 tmp_tags
[*tag_i
] = pos
;
404 if (reach_pos
[trans_i
->state_id
].pos
< pos
)
406 /* Found an unvisited node. */
407 reach_next_i
->state
= trans_i
->state
;
408 tmp_iptr
= reach_next_i
->tags
;
409 reach_next_i
->tags
= tmp_tags
;
411 reach_pos
[trans_i
->state_id
].pos
= pos
;
412 reach_pos
[trans_i
->state_id
].tags
= &reach_next_i
->tags
;
414 if (reach_next_i
->state
== tnfa
->final
417 && reach_next_i
->tags
[0] <= match_tags
[0])))
421 for (i
= 0; i
< num_tags
; i
++)
422 match_tags
[i
] = reach_next_i
->tags
[i
];
429 assert(reach_pos
[trans_i
->state_id
].pos
== pos
);
430 /* Another path has also reached this state. We choose
431 the winner by examining the tag values for both
433 if (tre_tag_order(num_tags
, tnfa
->tag_directions
,
435 *reach_pos
[trans_i
->state_id
].tags
))
437 /* The new path wins. */
438 tmp_iptr
= *reach_pos
[trans_i
->state_id
].tags
;
439 *reach_pos
[trans_i
->state_id
].tags
= tmp_tags
;
440 if (trans_i
->state
== tnfa
->final
)
444 for (i
= 0; i
< num_tags
; i
++)
445 match_tags
[i
] = tmp_tags
[i
];
453 reach_next_i
->state
= NULL
;
456 *match_end_ofs
= match_eo
;
457 ret
= match_eo
>= 0 ? REG_OK
: REG_NOMATCH
;
465 /***********************************************************************
466 from tre-match-backtrack.c
467 ***********************************************************************/
470 This matcher is for regexps that use back referencing. Regexp matching
471 with back referencing is an NP-complete problem on the number of back
472 references. The easiest way to match them is to use a backtracking
473 routine which basically goes through all possible paths in the TNFA
474 and chooses the one which results in the best (leftmost and longest)
475 match. This can be spectacularly expensive and may run out of stack
476 space, but there really is no better known generic algorithm. Quoting
477 Henry Spencer from comp.compilers:
478 <URL: http://compilers.iecc.com/comparch/article/93-03-102>
480 POSIX.2 REs require longest match, which is really exciting to
481 implement since the obsolete ("basic") variant also includes
482 \<digit>. I haven't found a better way of tackling this than doing
483 a preliminary match using a DFA (or simulation) on a modified RE
484 that just replicates subREs for \<digit>, and then doing a
485 backtracking match to determine whether the subRE matches were
486 right. This can be rather slow, but I console myself with the
487 thought that people who use \<digit> deserve very slow execution.
488 (Pun unintentional but very appropriate.)
494 const char *str_byte
;
495 tre_tnfa_transition_t
*state
;
501 #endif /* TRE_MBSTATE */
502 } tre_backtrack_item_t
;
504 typedef struct tre_backtrack_struct
{
505 tre_backtrack_item_t item
;
506 struct tre_backtrack_struct
*prev
;
507 struct tre_backtrack_struct
*next
;
511 #define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate)
512 #define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate
513 #else /* !TRE_MBSTATE */
514 #define BT_STACK_MBSTATE_IN
515 #define BT_STACK_MBSTATE_OUT
516 #endif /* !TRE_MBSTATE */
518 #define tre_bt_mem_new tre_mem_new
519 #define tre_bt_mem_alloc tre_mem_alloc
520 #define tre_bt_mem_destroy tre_mem_destroy
523 #define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \
530 s = tre_bt_mem_alloc(mem, sizeof(*s)); \
533 tre_bt_mem_destroy(mem); \
539 xfree(states_seen); \
544 s->item.tags = tre_bt_mem_alloc(mem, \
545 sizeof(*tags) * tnfa->num_tags); \
548 tre_bt_mem_destroy(mem); \
554 xfree(states_seen); \
561 stack = stack->next; \
562 stack->item.pos = (_pos); \
563 stack->item.str_byte = (_str_byte); \
564 stack->item.state = (_state); \
565 stack->item.state_id = (_state_id); \
566 stack->item.next_c = (_next_c); \
567 for (i = 0; i < tnfa->num_tags; i++) \
568 stack->item.tags[i] = (_tags)[i]; \
569 BT_STACK_MBSTATE_IN; \
573 #define BT_STACK_POP() \
577 assert(stack->prev); \
578 pos = stack->item.pos; \
579 str_byte = stack->item.str_byte; \
580 state = stack->item.state; \
581 next_c = stack->item.next_c; \
582 for (i = 0; i < tnfa->num_tags; i++) \
583 tags[i] = stack->item.tags[i]; \
584 BT_STACK_MBSTATE_OUT; \
585 stack = stack->prev; \
590 #define MIN(a, b) ((a) <= (b) ? (a) : (b))
593 tre_tnfa_run_backtrack(const tre_tnfa_t
*tnfa
, const void *string
,
594 regoff_t
*match_tags
, int eflags
, regoff_t
*match_end_ofs
)
596 /* State variables required by GET_NEXT_WCHAR. */
597 tre_char_t prev_c
= 0, next_c
= 0;
598 const char *str_byte
= string
;
600 regoff_t pos_add_next
= 1;
603 #endif /* TRE_MBSTATE */
604 int reg_notbol
= eflags
& REG_NOTBOL
;
605 int reg_noteol
= eflags
& REG_NOTEOL
;
606 int reg_newline
= tnfa
->cflags
& REG_NEWLINE
;
608 /* These are used to remember the necessary values of the above
609 variables to return to the position where the current search
612 const char *str_byte_start
;
613 regoff_t pos_start
= -1;
615 mbstate_t mbstate_start
;
616 #endif /* TRE_MBSTATE */
618 /* End offset of best match so far, or -1 if no match found yet. */
619 regoff_t match_eo
= -1;
622 regoff_t
*tags
= NULL
;
623 /* Current TNFA state. */
624 tre_tnfa_transition_t
*state
;
625 int *states_seen
= NULL
;
627 /* Memory allocator to for allocating the backtracking stack. */
628 tre_mem_t mem
= tre_bt_mem_new();
630 /* The backtracking stack. */
631 tre_backtrack_t stack
;
633 tre_tnfa_transition_t
*trans_i
;
634 regmatch_t
*pmatch
= NULL
;
638 memset(&mbstate
, '\0', sizeof(mbstate
));
639 #endif /* TRE_MBSTATE */
643 stack
= tre_bt_mem_alloc(mem
, sizeof(*stack
));
654 tags
= xmalloc(sizeof(*tags
) * tnfa
->num_tags
);
661 if (tnfa
->num_submatches
)
663 pmatch
= xmalloc(sizeof(*pmatch
) * tnfa
->num_submatches
);
670 if (tnfa
->num_states
)
672 states_seen
= xmalloc(sizeof(*states_seen
) * tnfa
->num_states
);
683 for (i
= 0; i
< tnfa
->num_tags
; i
++)
689 for (i
= 0; i
< tnfa
->num_states
; i
++)
697 next_c_start
= next_c
;
698 str_byte_start
= str_byte
;
700 mbstate_start
= mbstate
;
701 #endif /* TRE_MBSTATE */
703 /* Handle initial states. */
705 for (trans_i
= tnfa
->initial
; trans_i
->state
; trans_i
++)
707 if (trans_i
->assertions
&& CHECK_ASSERTIONS(trans_i
->assertions
))
713 /* Start from this state. */
714 state
= trans_i
->state
;
715 next_tags
= trans_i
->tags
;
719 /* Backtrack to this state. */
720 BT_STACK_PUSH(pos
, str_byte
, 0, trans_i
->state
,
721 trans_i
->state_id
, next_c
, tags
, mbstate
);
723 int *tmp
= trans_i
->tags
;
726 stack
->item
.tags
[*tmp
++] = pos
;
732 for (; *next_tags
>= 0; next_tags
++)
733 tags
[*next_tags
] = pos
;
741 tre_tnfa_transition_t
*next_state
;
744 if (state
== tnfa
->final
)
749 && tre_tag_order(tnfa
->num_tags
, tnfa
->tag_directions
,
753 /* This match wins the previous match. */
756 for (i
= 0; i
< tnfa
->num_tags
; i
++)
757 match_tags
[i
] = tags
[i
];
759 /* Our TNFAs never have transitions leaving from the final state,
760 so we jump right to backtracking. */
764 /* Go to the next character in the input string. */
767 if (trans_i
->state
&& trans_i
->assertions
& ASSERT_BACKREF
)
769 /* This is a back reference state. All transitions leaving from
770 this state have the same back reference "assertion". Instead
771 of reading the next character, we match the back reference. */
773 int bt
= trans_i
->u
.backref
;
777 /* Get the substring we need to match against. Remember to
778 turn off REG_NOSUB temporarily. */
779 tre_fill_pmatch(bt
+ 1, pmatch
, tnfa
->cflags
& ~REG_NOSUB
,
781 so
= pmatch
[bt
].rm_so
;
782 eo
= pmatch
[bt
].rm_eo
;
785 result
= strncmp((const char*)string
+ so
, str_byte
- 1,
790 /* Back reference matched. Check for infinite loop. */
793 if (empty_br_match
&& states_seen
[trans_i
->state_id
])
798 states_seen
[trans_i
->state_id
] = empty_br_match
;
800 /* Advance in input string and resync `prev_c', `next_c'
802 str_byte
+= bt_len
- 1;
813 /* Check for end of string. */
817 /* Read the next character. */
822 for (trans_i
= state
; trans_i
->state
; trans_i
++)
824 if (trans_i
->code_min
<= (tre_cint_t
)prev_c
825 && trans_i
->code_max
>= (tre_cint_t
)prev_c
)
827 if (trans_i
->assertions
828 && (CHECK_ASSERTIONS(trans_i
->assertions
)
829 || CHECK_CHAR_CLASSES(trans_i
, tnfa
, eflags
)))
834 if (next_state
== NULL
)
836 /* First matching transition. */
837 next_state
= trans_i
->state
;
838 next_tags
= trans_i
->tags
;
842 /* Second matching transition. We may need to backtrack here
843 to take this transition instead of the first one, so we
844 push this transition in the backtracking stack so we can
845 jump back here if needed. */
846 BT_STACK_PUSH(pos
, str_byte
, 0, trans_i
->state
,
847 trans_i
->state_id
, next_c
, tags
, mbstate
);
850 for (tmp
= trans_i
->tags
; tmp
&& *tmp
>= 0; tmp
++)
851 stack
->item
.tags
[*tmp
] = pos
;
853 #if 0 /* XXX - it's important not to look at all transitions here to keep
861 if (next_state
!= NULL
)
863 /* Matching transitions were found. Take the first one. */
866 /* Update the tag values. */
868 while (*next_tags
>= 0)
869 tags
[*next_tags
++] = pos
;
874 /* A matching transition was not found. Try to backtrack. */
877 if (stack
->item
.state
->assertions
& ASSERT_BACKREF
)
879 states_seen
[stack
->item
.state_id
] = 0;
884 else if (match_eo
< 0)
886 /* Try starting from a later position in the input string. */
887 /* Check for end of string. */
892 next_c
= next_c_start
;
894 mbstate
= mbstate_start
;
895 #endif /* TRE_MBSTATE */
896 str_byte
= str_byte_start
;
906 ret
= match_eo
>= 0 ? REG_OK
: REG_NOMATCH
;
907 *match_end_ofs
= match_eo
;
910 tre_bt_mem_destroy(mem
);
911 #ifndef TRE_USE_ALLOCA
918 #endif /* !TRE_USE_ALLOCA */
923 /***********************************************************************
925 ***********************************************************************/
927 /* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match
930 tre_fill_pmatch(size_t nmatch
, regmatch_t pmatch
[], int cflags
,
931 const tre_tnfa_t
*tnfa
, regoff_t
*tags
, regoff_t match_eo
)
933 tre_submatch_data_t
*submatch_data
;
938 if (match_eo
>= 0 && !(cflags
& REG_NOSUB
))
940 /* Construct submatch offsets from the tags. */
941 submatch_data
= tnfa
->submatch_data
;
942 while (i
< tnfa
->num_submatches
&& i
< nmatch
)
944 if (submatch_data
[i
].so_tag
== tnfa
->end_tag
)
945 pmatch
[i
].rm_so
= match_eo
;
947 pmatch
[i
].rm_so
= tags
[submatch_data
[i
].so_tag
];
949 if (submatch_data
[i
].eo_tag
== tnfa
->end_tag
)
950 pmatch
[i
].rm_eo
= match_eo
;
952 pmatch
[i
].rm_eo
= tags
[submatch_data
[i
].eo_tag
];
954 /* If either of the endpoints were not used, this submatch
955 was not part of the match. */
956 if (pmatch
[i
].rm_so
== -1 || pmatch
[i
].rm_eo
== -1)
957 pmatch
[i
].rm_so
= pmatch
[i
].rm_eo
= -1;
961 /* Reset all submatches that are not within all of their parent
964 while (i
< tnfa
->num_submatches
&& i
< nmatch
)
966 if (pmatch
[i
].rm_eo
== -1)
967 assert(pmatch
[i
].rm_so
== -1);
968 assert(pmatch
[i
].rm_so
<= pmatch
[i
].rm_eo
);
970 parents
= submatch_data
[i
].parents
;
972 for (j
= 0; parents
[j
] >= 0; j
++)
974 if (pmatch
[i
].rm_so
< pmatch
[parents
[j
]].rm_so
975 || pmatch
[i
].rm_eo
> pmatch
[parents
[j
]].rm_eo
)
976 pmatch
[i
].rm_so
= pmatch
[i
].rm_eo
= -1;
984 pmatch
[i
].rm_so
= -1;
985 pmatch
[i
].rm_eo
= -1;
992 Wrapper functions for POSIX compatible regexp matching.
996 regexec(const regex_t
*restrict preg
, const char *restrict string
,
997 size_t nmatch
, regmatch_t pmatch
[restrict
], int eflags
)
999 tre_tnfa_t
*tnfa
= (void *)preg
->TRE_REGEX_T_FIELD
;
1000 reg_errcode_t status
;
1001 regoff_t
*tags
= NULL
, eo
;
1002 if (tnfa
->cflags
& REG_NOSUB
) nmatch
= 0;
1003 if (tnfa
->num_tags
> 0 && nmatch
> 0)
1005 tags
= xmalloc(sizeof(*tags
) * tnfa
->num_tags
);
1010 /* Dispatch to the appropriate matcher. */
1011 if (tnfa
->have_backrefs
)
1013 /* The regex has back references, use the backtracking matcher. */
1014 status
= tre_tnfa_run_backtrack(tnfa
, string
, tags
, eflags
, &eo
);
1018 /* Exact matching, no back references, use the parallel matcher. */
1019 status
= tre_tnfa_run_parallel(tnfa
, string
, tags
, eflags
, &eo
);
1022 if (status
== REG_OK
)
1023 /* A match was found, so fill the submatch registers. */
1024 tre_fill_pmatch(nmatch
, pmatch
, tnfa
->cflags
, tnfa
, tags
, eo
);