diff options
Diffstat (limited to 'libc-top-half/musl/src/regex/regexec.c')
| -rw-r--r-- | libc-top-half/musl/src/regex/regexec.c | 1028 |
1 files changed, 1028 insertions, 0 deletions
diff --git a/libc-top-half/musl/src/regex/regexec.c b/libc-top-half/musl/src/regex/regexec.c new file mode 100644 index 0000000..253b0e1 --- /dev/null +++ b/libc-top-half/musl/src/regex/regexec.c @@ -0,0 +1,1028 @@ +/* + regexec.c - TRE POSIX compatible matching functions (and more). + + Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi> + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS + ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*/ + +#include <stdlib.h> +#include <string.h> +#include <wchar.h> +#include <wctype.h> +#include <limits.h> +#include <stdint.h> + +#include <regex.h> + +#include "tre.h" + +#include <assert.h> + +static void +tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, + const tre_tnfa_t *tnfa, regoff_t *tags, regoff_t match_eo); + +/*********************************************************************** + from tre-match-utils.h +***********************************************************************/ + +#define GET_NEXT_WCHAR() do { \ + prev_c = next_c; pos += pos_add_next; \ + if ((pos_add_next = mbtowc(&next_c, str_byte, MB_LEN_MAX)) <= 0) { \ + if (pos_add_next < 0) { ret = REG_NOMATCH; goto error_exit; } \ + else pos_add_next++; \ + } \ + str_byte += pos_add_next; \ + } while (0) + +#define IS_WORD_CHAR(c) ((c) == L'_' || tre_isalnum(c)) + +#define CHECK_ASSERTIONS(assertions) \ + (((assertions & ASSERT_AT_BOL) \ + && (pos > 0 || reg_notbol) \ + && (prev_c != L'\n' || !reg_newline)) \ + || ((assertions & ASSERT_AT_EOL) \ + && (next_c != L'\0' || reg_noteol) \ + && (next_c != L'\n' || !reg_newline)) \ + || ((assertions & ASSERT_AT_BOW) \ + && (IS_WORD_CHAR(prev_c) || !IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_EOW) \ + && (!IS_WORD_CHAR(prev_c) || IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_WB) \ + && (pos != 0 && next_c != L'\0' \ + && IS_WORD_CHAR(prev_c) == IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_WB_NEG) \ + && (pos == 0 || next_c == L'\0' \ + || IS_WORD_CHAR(prev_c) != IS_WORD_CHAR(next_c)))) + +#define CHECK_CHAR_CLASSES(trans_i, tnfa, eflags) \ + (((trans_i->assertions & ASSERT_CHAR_CLASS) \ + && !(tnfa->cflags & REG_ICASE) \ + && !tre_isctype((tre_cint_t)prev_c, trans_i->u.class)) \ + || ((trans_i->assertions & ASSERT_CHAR_CLASS) \ + && (tnfa->cflags & REG_ICASE) \ + && !tre_isctype(tre_tolower((tre_cint_t)prev_c),trans_i->u.class) \ + && !tre_isctype(tre_toupper((tre_cint_t)prev_c),trans_i->u.class)) \ + || ((trans_i->assertions & ASSERT_CHAR_CLASS_NEG) \ + && tre_neg_char_classes_match(trans_i->neg_classes,(tre_cint_t)prev_c,\ + tnfa->cflags & REG_ICASE))) + + + + +/* Returns 1 if `t1' wins `t2', 0 otherwise. */ +static int +tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions, + regoff_t *t1, regoff_t *t2) +{ + int i; + for (i = 0; i < num_tags; i++) + { + if (tag_directions[i] == TRE_TAG_MINIMIZE) + { + if (t1[i] < t2[i]) + return 1; + if (t1[i] > t2[i]) + return 0; + } + else + { + if (t1[i] > t2[i]) + return 1; + if (t1[i] < t2[i]) + return 0; + } + } + /* assert(0);*/ + return 0; +} + +static int +tre_neg_char_classes_match(tre_ctype_t *classes, tre_cint_t wc, int icase) +{ + while (*classes != (tre_ctype_t)0) + if ((!icase && tre_isctype(wc, *classes)) + || (icase && (tre_isctype(tre_toupper(wc), *classes) + || tre_isctype(tre_tolower(wc), *classes)))) + return 1; /* Match. */ + else + classes++; + return 0; /* No match. */ +} + + +/*********************************************************************** + from tre-match-parallel.c +***********************************************************************/ + +/* + This algorithm searches for matches basically by reading characters + in the searched string one by one, starting at the beginning. All + matching paths in the TNFA are traversed in parallel. When two or + more paths reach the same state, exactly one is chosen according to + tag ordering rules; if returning submatches is not required it does + not matter which path is chosen. + + The worst case time required for finding the leftmost and longest + match, or determining that there is no match, is always linearly + dependent on the length of the text being searched. + + This algorithm cannot handle TNFAs with back referencing nodes. + See `tre-match-backtrack.c'. +*/ + +typedef struct { + tre_tnfa_transition_t *state; + regoff_t *tags; +} tre_tnfa_reach_t; + +typedef struct { + regoff_t pos; + regoff_t **tags; +} tre_reach_pos_t; + + +static reg_errcode_t +tre_tnfa_run_parallel(const tre_tnfa_t *tnfa, const void *string, + regoff_t *match_tags, int eflags, + regoff_t *match_end_ofs) +{ + /* State variables required by GET_NEXT_WCHAR. */ + tre_char_t prev_c = 0, next_c = 0; + const char *str_byte = string; + regoff_t pos = -1; + regoff_t pos_add_next = 1; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ + int reg_notbol = eflags & REG_NOTBOL; + int reg_noteol = eflags & REG_NOTEOL; + int reg_newline = tnfa->cflags & REG_NEWLINE; + reg_errcode_t ret; + + char *buf; + tre_tnfa_transition_t *trans_i; + tre_tnfa_reach_t *reach, *reach_next, *reach_i, *reach_next_i; + tre_reach_pos_t *reach_pos; + int *tag_i; + int num_tags, i; + + regoff_t match_eo = -1; /* end offset of match (-1 if no match found yet) */ + int new_match = 0; + regoff_t *tmp_tags = NULL; + regoff_t *tmp_iptr; + +#ifdef TRE_MBSTATE + memset(&mbstate, '\0', sizeof(mbstate)); +#endif /* TRE_MBSTATE */ + + if (!match_tags) + num_tags = 0; + else + num_tags = tnfa->num_tags; + + /* Allocate memory for temporary data required for matching. This needs to + be done for every matching operation to be thread safe. This allocates + everything in a single large block with calloc(). */ + { + size_t tbytes, rbytes, pbytes, xbytes, total_bytes; + char *tmp_buf; + + /* Ensure that tbytes and xbytes*num_states cannot overflow, and that + * they don't contribute more than 1/8 of SIZE_MAX to total_bytes. */ + if (num_tags > SIZE_MAX/(8 * sizeof(regoff_t) * tnfa->num_states)) + return REG_ESPACE; + + /* Likewise check rbytes. */ + if (tnfa->num_states+1 > SIZE_MAX/(8 * sizeof(*reach_next))) + return REG_ESPACE; + + /* Likewise check pbytes. */ + if (tnfa->num_states > SIZE_MAX/(8 * sizeof(*reach_pos))) + return REG_ESPACE; + + /* Compute the length of the block we need. */ + tbytes = sizeof(*tmp_tags) * num_tags; + rbytes = sizeof(*reach_next) * (tnfa->num_states + 1); + pbytes = sizeof(*reach_pos) * tnfa->num_states; + xbytes = sizeof(regoff_t) * num_tags; + total_bytes = + (sizeof(long) - 1) * 4 /* for alignment paddings */ + + (rbytes + xbytes * tnfa->num_states) * 2 + tbytes + pbytes; + + /* Allocate the memory. */ + buf = calloc(total_bytes, 1); + if (buf == NULL) + return REG_ESPACE; + + /* Get the various pointers within tmp_buf (properly aligned). */ + tmp_tags = (void *)buf; + tmp_buf = buf + tbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach_next = (void *)tmp_buf; + tmp_buf += rbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach = (void *)tmp_buf; + tmp_buf += rbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach_pos = (void *)tmp_buf; + tmp_buf += pbytes; + tmp_buf += ALIGN(tmp_buf, long); + for (i = 0; i < tnfa->num_states; i++) + { + reach[i].tags = (void *)tmp_buf; + tmp_buf += xbytes; + reach_next[i].tags = (void *)tmp_buf; + tmp_buf += xbytes; + } + } + + for (i = 0; i < tnfa->num_states; i++) + reach_pos[i].pos = -1; + + GET_NEXT_WCHAR(); + pos = 0; + + reach_next_i = reach_next; + while (1) + { + /* If no match found yet, add the initial states to `reach_next'. */ + if (match_eo < 0) + { + trans_i = tnfa->initial; + while (trans_i->state != NULL) + { + if (reach_pos[trans_i->state_id].pos < pos) + { + if (trans_i->assertions + && CHECK_ASSERTIONS(trans_i->assertions)) + { + trans_i++; + continue; + } + + reach_next_i->state = trans_i->state; + for (i = 0; i < num_tags; i++) + reach_next_i->tags[i] = -1; + tag_i = trans_i->tags; + if (tag_i) + while (*tag_i >= 0) + { + if (*tag_i < num_tags) + reach_next_i->tags[*tag_i] = pos; + tag_i++; + } + if (reach_next_i->state == tnfa->final) + { + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = reach_next_i->tags[i]; + } + reach_pos[trans_i->state_id].pos = pos; + reach_pos[trans_i->state_id].tags = &reach_next_i->tags; + reach_next_i++; + } + trans_i++; + } + reach_next_i->state = NULL; + } + else + { + if (num_tags == 0 || reach_next_i == reach_next) + /* We have found a match. */ + break; + } + + /* Check for end of string. */ + if (!next_c) break; + + GET_NEXT_WCHAR(); + + /* Swap `reach' and `reach_next'. */ + reach_i = reach; + reach = reach_next; + reach_next = reach_i; + + /* For each state in `reach', weed out states that don't fulfill the + minimal matching conditions. */ + if (tnfa->num_minimals && new_match) + { + new_match = 0; + reach_next_i = reach_next; + for (reach_i = reach; reach_i->state; reach_i++) + { + int skip = 0; + for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2) + { + int end = tnfa->minimal_tags[i]; + int start = tnfa->minimal_tags[i + 1]; + if (end >= num_tags) + { + skip = 1; + break; + } + else if (reach_i->tags[start] == match_tags[start] + && reach_i->tags[end] < match_tags[end]) + { + skip = 1; + break; + } + } + if (!skip) + { + reach_next_i->state = reach_i->state; + tmp_iptr = reach_next_i->tags; + reach_next_i->tags = reach_i->tags; + reach_i->tags = tmp_iptr; + reach_next_i++; + } + } + reach_next_i->state = NULL; + + /* Swap `reach' and `reach_next'. */ + reach_i = reach; + reach = reach_next; + reach_next = reach_i; + } + + /* For each state in `reach' see if there is a transition leaving with + the current input symbol to a state not yet in `reach_next', and + add the destination states to `reach_next'. */ + reach_next_i = reach_next; + for (reach_i = reach; reach_i->state; reach_i++) + { + for (trans_i = reach_i->state; trans_i->state; trans_i++) + { + /* Does this transition match the input symbol? */ + if (trans_i->code_min <= (tre_cint_t)prev_c && + trans_i->code_max >= (tre_cint_t)prev_c) + { + if (trans_i->assertions + && (CHECK_ASSERTIONS(trans_i->assertions) + || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) + { + continue; + } + + /* Compute the tags after this transition. */ + for (i = 0; i < num_tags; i++) + tmp_tags[i] = reach_i->tags[i]; + tag_i = trans_i->tags; + if (tag_i != NULL) + while (*tag_i >= 0) + { + if (*tag_i < num_tags) + tmp_tags[*tag_i] = pos; + tag_i++; + } + + if (reach_pos[trans_i->state_id].pos < pos) + { + /* Found an unvisited node. */ + reach_next_i->state = trans_i->state; + tmp_iptr = reach_next_i->tags; + reach_next_i->tags = tmp_tags; + tmp_tags = tmp_iptr; + reach_pos[trans_i->state_id].pos = pos; + reach_pos[trans_i->state_id].tags = &reach_next_i->tags; + + if (reach_next_i->state == tnfa->final + && (match_eo == -1 + || (num_tags > 0 + && reach_next_i->tags[0] <= match_tags[0]))) + { + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = reach_next_i->tags[i]; + } + reach_next_i++; + + } + else + { + assert(reach_pos[trans_i->state_id].pos == pos); + /* Another path has also reached this state. We choose + the winner by examining the tag values for both + paths. */ + if (tre_tag_order(num_tags, tnfa->tag_directions, + tmp_tags, + *reach_pos[trans_i->state_id].tags)) + { + /* The new path wins. */ + tmp_iptr = *reach_pos[trans_i->state_id].tags; + *reach_pos[trans_i->state_id].tags = tmp_tags; + if (trans_i->state == tnfa->final) + { + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = tmp_tags[i]; + } + tmp_tags = tmp_iptr; + } + } + } + } + } + reach_next_i->state = NULL; + } + + *match_end_ofs = match_eo; + ret = match_eo >= 0 ? REG_OK : REG_NOMATCH; +error_exit: + xfree(buf); + return ret; +} + + + +/*********************************************************************** + from tre-match-backtrack.c +***********************************************************************/ + +/* + This matcher is for regexps that use back referencing. Regexp matching + with back referencing is an NP-complete problem on the number of back + references. The easiest way to match them is to use a backtracking + routine which basically goes through all possible paths in the TNFA + and chooses the one which results in the best (leftmost and longest) + match. This can be spectacularly expensive and may run out of stack + space, but there really is no better known generic algorithm. Quoting + Henry Spencer from comp.compilers: + <URL: http://compilers.iecc.com/comparch/article/93-03-102> + + POSIX.2 REs require longest match, which is really exciting to + implement since the obsolete ("basic") variant also includes + \<digit>. I haven't found a better way of tackling this than doing + a preliminary match using a DFA (or simulation) on a modified RE + that just replicates subREs for \<digit>, and then doing a + backtracking match to determine whether the subRE matches were + right. This can be rather slow, but I console myself with the + thought that people who use \<digit> deserve very slow execution. + (Pun unintentional but very appropriate.) + +*/ + +typedef struct { + regoff_t pos; + const char *str_byte; + tre_tnfa_transition_t *state; + int state_id; + int next_c; + regoff_t *tags; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ +} tre_backtrack_item_t; + +typedef struct tre_backtrack_struct { + tre_backtrack_item_t item; + struct tre_backtrack_struct *prev; + struct tre_backtrack_struct *next; +} *tre_backtrack_t; + +#ifdef TRE_MBSTATE +#define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate) +#define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate +#else /* !TRE_MBSTATE */ +#define BT_STACK_MBSTATE_IN +#define BT_STACK_MBSTATE_OUT +#endif /* !TRE_MBSTATE */ + +#define tre_bt_mem_new tre_mem_new +#define tre_bt_mem_alloc tre_mem_alloc +#define tre_bt_mem_destroy tre_mem_destroy + + +#define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \ + do \ + { \ + int i; \ + if (!stack->next) \ + { \ + tre_backtrack_t s; \ + s = tre_bt_mem_alloc(mem, sizeof(*s)); \ + if (!s) \ + { \ + tre_bt_mem_destroy(mem); \ + if (tags) \ + xfree(tags); \ + if (pmatch) \ + xfree(pmatch); \ + if (states_seen) \ + xfree(states_seen); \ + return REG_ESPACE; \ + } \ + s->prev = stack; \ + s->next = NULL; \ + s->item.tags = tre_bt_mem_alloc(mem, \ + sizeof(*tags) * tnfa->num_tags); \ + if (!s->item.tags) \ + { \ + tre_bt_mem_destroy(mem); \ + if (tags) \ + xfree(tags); \ + if (pmatch) \ + xfree(pmatch); \ + if (states_seen) \ + xfree(states_seen); \ + return REG_ESPACE; \ + } \ + stack->next = s; \ + stack = s; \ + } \ + else \ + stack = stack->next; \ + stack->item.pos = (_pos); \ + stack->item.str_byte = (_str_byte); \ + stack->item.state = (_state); \ + stack->item.state_id = (_state_id); \ + stack->item.next_c = (_next_c); \ + for (i = 0; i < tnfa->num_tags; i++) \ + stack->item.tags[i] = (_tags)[i]; \ + BT_STACK_MBSTATE_IN; \ + } \ + while (0) + +#define BT_STACK_POP() \ + do \ + { \ + int i; \ + assert(stack->prev); \ + pos = stack->item.pos; \ + str_byte = stack->item.str_byte; \ + state = stack->item.state; \ + next_c = stack->item.next_c; \ + for (i = 0; i < tnfa->num_tags; i++) \ + tags[i] = stack->item.tags[i]; \ + BT_STACK_MBSTATE_OUT; \ + stack = stack->prev; \ + } \ + while (0) + +#undef MIN +#define MIN(a, b) ((a) <= (b) ? (a) : (b)) + +static reg_errcode_t +tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, + regoff_t *match_tags, int eflags, regoff_t *match_end_ofs) +{ + /* State variables required by GET_NEXT_WCHAR. */ + tre_char_t prev_c = 0, next_c = 0; + const char *str_byte = string; + regoff_t pos = 0; + regoff_t pos_add_next = 1; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ + int reg_notbol = eflags & REG_NOTBOL; + int reg_noteol = eflags & REG_NOTEOL; + int reg_newline = tnfa->cflags & REG_NEWLINE; + + /* These are used to remember the necessary values of the above + variables to return to the position where the current search + started from. */ + int next_c_start; + const char *str_byte_start; + regoff_t pos_start = -1; +#ifdef TRE_MBSTATE + mbstate_t mbstate_start; +#endif /* TRE_MBSTATE */ + + /* End offset of best match so far, or -1 if no match found yet. */ + regoff_t match_eo = -1; + /* Tag arrays. */ + int *next_tags; + regoff_t *tags = NULL; + /* Current TNFA state. */ + tre_tnfa_transition_t *state; + int *states_seen = NULL; + + /* Memory allocator to for allocating the backtracking stack. */ + tre_mem_t mem = tre_bt_mem_new(); + + /* The backtracking stack. */ + tre_backtrack_t stack; + + tre_tnfa_transition_t *trans_i; + regmatch_t *pmatch = NULL; + int ret; + +#ifdef TRE_MBSTATE + memset(&mbstate, '\0', sizeof(mbstate)); +#endif /* TRE_MBSTATE */ + + if (!mem) + return REG_ESPACE; + stack = tre_bt_mem_alloc(mem, sizeof(*stack)); + if (!stack) + { + ret = REG_ESPACE; + goto error_exit; + } + stack->prev = NULL; + stack->next = NULL; + + if (tnfa->num_tags) + { + tags = xmalloc(sizeof(*tags) * tnfa->num_tags); + if (!tags) + { + ret = REG_ESPACE; + goto error_exit; + } + } + if (tnfa->num_submatches) + { + pmatch = xmalloc(sizeof(*pmatch) * tnfa->num_submatches); + if (!pmatch) + { + ret = REG_ESPACE; + goto error_exit; + } + } + if (tnfa->num_states) + { + states_seen = xmalloc(sizeof(*states_seen) * tnfa->num_states); + if (!states_seen) + { + ret = REG_ESPACE; + goto error_exit; + } + } + + retry: + { + int i; + for (i = 0; i < tnfa->num_tags; i++) + { + tags[i] = -1; + if (match_tags) + match_tags[i] = -1; + } + for (i = 0; i < tnfa->num_states; i++) + states_seen[i] = 0; + } + + state = NULL; + pos = pos_start; + GET_NEXT_WCHAR(); + pos_start = pos; + next_c_start = next_c; + str_byte_start = str_byte; +#ifdef TRE_MBSTATE + mbstate_start = mbstate; +#endif /* TRE_MBSTATE */ + + /* Handle initial states. */ + next_tags = NULL; + for (trans_i = tnfa->initial; trans_i->state; trans_i++) + { + if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions)) + { + continue; + } + if (state == NULL) + { + /* Start from this state. */ + state = trans_i->state; + next_tags = trans_i->tags; + } + else + { + /* Backtrack to this state. */ + BT_STACK_PUSH(pos, str_byte, 0, trans_i->state, + trans_i->state_id, next_c, tags, mbstate); + { + int *tmp = trans_i->tags; + if (tmp) + while (*tmp >= 0) + stack->item.tags[*tmp++] = pos; + } + } + } + + if (next_tags) + for (; *next_tags >= 0; next_tags++) + tags[*next_tags] = pos; + + + if (state == NULL) + goto backtrack; + + while (1) + { + tre_tnfa_transition_t *next_state; + int empty_br_match; + + if (state == tnfa->final) + { + if (match_eo < pos + || (match_eo == pos + && match_tags + && tre_tag_order(tnfa->num_tags, tnfa->tag_directions, + tags, match_tags))) + { + int i; + /* This match wins the previous match. */ + match_eo = pos; + if (match_tags) + for (i = 0; i < tnfa->num_tags; i++) + match_tags[i] = tags[i]; + } + /* Our TNFAs never have transitions leaving from the final state, + so we jump right to backtracking. */ + goto backtrack; + } + + /* Go to the next character in the input string. */ + empty_br_match = 0; + trans_i = state; + if (trans_i->state && trans_i->assertions & ASSERT_BACKREF) + { + /* This is a back reference state. All transitions leaving from + this state have the same back reference "assertion". Instead + of reading the next character, we match the back reference. */ + regoff_t so, eo; + int bt = trans_i->u.backref; + regoff_t bt_len; + int result; + + /* Get the substring we need to match against. Remember to + turn off REG_NOSUB temporarily. */ + tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB, + tnfa, tags, pos); + so = pmatch[bt].rm_so; + eo = pmatch[bt].rm_eo; + bt_len = eo - so; + + result = strncmp((const char*)string + so, str_byte - 1, + (size_t)bt_len); + + if (result == 0) + { + /* Back reference matched. Check for infinite loop. */ + if (bt_len == 0) + empty_br_match = 1; + if (empty_br_match && states_seen[trans_i->state_id]) + { + goto backtrack; + } + + states_seen[trans_i->state_id] = empty_br_match; + + /* Advance in input string and resync `prev_c', `next_c' + and pos. */ + str_byte += bt_len - 1; + pos += bt_len - 1; + GET_NEXT_WCHAR(); + } + else + { + goto backtrack; + } + } + else + { + /* Check for end of string. */ + if (next_c == L'\0') + goto backtrack; + + /* Read the next character. */ + GET_NEXT_WCHAR(); + } + + next_state = NULL; + for (trans_i = state; trans_i->state; trans_i++) + { + if (trans_i->code_min <= (tre_cint_t)prev_c + && trans_i->code_max >= (tre_cint_t)prev_c) + { + if (trans_i->assertions + && (CHECK_ASSERTIONS(trans_i->assertions) + || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) + { + continue; + } + + if (next_state == NULL) + { + /* First matching transition. */ + next_state = trans_i->state; + next_tags = trans_i->tags; + } + else + { + /* Second matching transition. We may need to backtrack here + to take this transition instead of the first one, so we + push this transition in the backtracking stack so we can + jump back here if needed. */ + BT_STACK_PUSH(pos, str_byte, 0, trans_i->state, + trans_i->state_id, next_c, tags, mbstate); + { + int *tmp; + for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++) + stack->item.tags[*tmp] = pos; + } +#if 0 /* XXX - it's important not to look at all transitions here to keep + the stack small! */ + break; +#endif + } + } + } + + if (next_state != NULL) + { + /* Matching transitions were found. Take the first one. */ + state = next_state; + + /* Update the tag values. */ + if (next_tags) + while (*next_tags >= 0) + tags[*next_tags++] = pos; + } + else + { + backtrack: + /* A matching transition was not found. Try to backtrack. */ + if (stack->prev) + { + if (stack->item.state->assertions & ASSERT_BACKREF) + { + states_seen[stack->item.state_id] = 0; + } + + BT_STACK_POP(); + } + else if (match_eo < 0) + { + /* Try starting from a later position in the input string. */ + /* Check for end of string. */ + if (next_c == L'\0') + { + break; + } + next_c = next_c_start; +#ifdef TRE_MBSTATE + mbstate = mbstate_start; +#endif /* TRE_MBSTATE */ + str_byte = str_byte_start; + goto retry; + } + else + { + break; + } + } + } + + ret = match_eo >= 0 ? REG_OK : REG_NOMATCH; + *match_end_ofs = match_eo; + + error_exit: + tre_bt_mem_destroy(mem); +#ifndef TRE_USE_ALLOCA + if (tags) + xfree(tags); + if (pmatch) + xfree(pmatch); + if (states_seen) + xfree(states_seen); +#endif /* !TRE_USE_ALLOCA */ + + return ret; +} + +/*********************************************************************** + from regexec.c +***********************************************************************/ + +/* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match + endpoint values. */ +static void +tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, + const tre_tnfa_t *tnfa, regoff_t *tags, regoff_t match_eo) +{ + tre_submatch_data_t *submatch_data; + unsigned int i, j; + int *parents; + + i = 0; + if (match_eo >= 0 && !(cflags & REG_NOSUB)) + { + /* Construct submatch offsets from the tags. */ + submatch_data = tnfa->submatch_data; + while (i < tnfa->num_submatches && i < nmatch) + { + if (submatch_data[i].so_tag == tnfa->end_tag) + pmatch[i].rm_so = match_eo; + else + pmatch[i].rm_so = tags[submatch_data[i].so_tag]; + + if (submatch_data[i].eo_tag == tnfa->end_tag) + pmatch[i].rm_eo = match_eo; + else + pmatch[i].rm_eo = tags[submatch_data[i].eo_tag]; + + /* If either of the endpoints were not used, this submatch + was not part of the match. */ + if (pmatch[i].rm_so == -1 || pmatch[i].rm_eo == -1) + pmatch[i].rm_so = pmatch[i].rm_eo = -1; + + i++; + } + /* Reset all submatches that are not within all of their parent + submatches. */ + i = 0; + while (i < tnfa->num_submatches && i < nmatch) + { + if (pmatch[i].rm_eo == -1) + assert(pmatch[i].rm_so == -1); + assert(pmatch[i].rm_so <= pmatch[i].rm_eo); + + parents = submatch_data[i].parents; + if (parents != NULL) + for (j = 0; parents[j] >= 0; j++) + { + if (pmatch[i].rm_so < pmatch[parents[j]].rm_so + || pmatch[i].rm_eo > pmatch[parents[j]].rm_eo) + pmatch[i].rm_so = pmatch[i].rm_eo = -1; + } + i++; + } + } + + while (i < nmatch) + { + pmatch[i].rm_so = -1; + pmatch[i].rm_eo = -1; + i++; + } +} + + +/* + Wrapper functions for POSIX compatible regexp matching. +*/ + +int +regexec(const regex_t *restrict preg, const char *restrict string, + size_t nmatch, regmatch_t pmatch[restrict], int eflags) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + reg_errcode_t status; + regoff_t *tags = NULL, eo; + if (tnfa->cflags & REG_NOSUB) nmatch = 0; + if (tnfa->num_tags > 0 && nmatch > 0) + { + tags = xmalloc(sizeof(*tags) * tnfa->num_tags); + if (tags == NULL) + return REG_ESPACE; + } + + /* Dispatch to the appropriate matcher. */ + if (tnfa->have_backrefs) + { + /* The regex has back references, use the backtracking matcher. */ + status = tre_tnfa_run_backtrack(tnfa, string, tags, eflags, &eo); + } + else + { + /* Exact matching, no back references, use the parallel matcher. */ + status = tre_tnfa_run_parallel(tnfa, string, tags, eflags, &eo); + } + + if (status == REG_OK) + /* A match was found, so fill the submatch registers. */ + tre_fill_pmatch(nmatch, pmatch, tnfa->cflags, tnfa, tags, eo); + if (tags) + xfree(tags); + return status; +} |