diff options
| -rw-r--r-- | ChangeLog | 45 | ||||
| -rw-r--r-- | posix/regcomp.c | 80 | ||||
| -rw-r--r-- | posix/regex_internal.c | 16 | ||||
| -rw-r--r-- | posix/regex_internal.h | 6 | ||||
| -rw-r--r-- | posix/regexec.c | 435 |
5 files changed, 362 insertions, 220 deletions
diff --git a/ChangeLog b/ChangeLog index 052cd93fbe..8ae57ef7f2 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,50 @@ +2004-11-08 Ulrich Drepper <drepper@redhat.com> + + * posix/regcomp.c (utf8_sb_map): Define. + (free_dfa_content): Don't free dfa->sb_char if it's a pointer to + utf8_sb_map. + (init_dfa): Use utf8_sb_map instead of initializing memory when the + encoding is UTF-8. + 2004-11-03 Paolo Bonzini <bonzini@gnu.org> + * posix/regcomp.c (init_dfa): Get the codeset name outside glibc as + well. Check if it is spelled UTF8 as well as UTF-8, and check + case-insensitively. Set dfa->map_notascii manually when outside + glibc. + * posix/regex_internal.c (build_wcs_upper_buffer) [!_LIBC]: Enable + optimizations based on map_notascii. + * posix/regex_internal.h [HAVE_LANGINFO_H || HAVE_LANGINFO_CODESET + || _LIBC]: Include langinfo.h. + + * posix/regex_internal.h (struct re_backref_cache_entry): Add "more" + field. + * posix/regexec.c (check_dst_limits): Hoist computation of the source + and destination bkref_idx out of the loop. Pass it to + check_dst_limits_calc_pos. + (check_dst_limits_calc_pos_1): New function, containing the recursive + loop of check_dst_limits_calc_pos; uses the "more" field of + struct re_backref_cache to control the loop. + (check_dst_limits_calc_pos): Store into "boundaries" the position + relative to lim's start and end positions. Do not accept eclosures, + accept bkref_idx instead. Call check_dst_limits_calc_pos_1 to do the + work. + (sift_states_bkref): Use the "more" field of struct re_backref_cache + to control the loop. A big "if" was turned into a continue and the + function was reindented. + (get_subexp): Use the "more" field of struct re_backref_cache + to control the loop. + (match_ctx_add_entry): Initialize the bkref_ents' "more" field. + (search_cur_bkref_entry): Return -1 if out of bounds. + + * posix/regexec.c (empty_set): Remove. + (sift_states_backward): Remove cur_src variable. Move inner loop + to build_sifted_states. + (build_sifted_states): Extract from sift_states_backward. Do not + use empty_set. + (update_cur_sifted_state): Do not use empty_set. Special case + dest_nodes->nelem == 0. + * posix/regex_internal.h (struct re_backref_cache_entry): Remove flag field. (struct re_sift_context_t): Remove cur_bkref, cls_subexp_idx, diff --git a/posix/regcomp.c b/posix/regcomp.c index 9b435a885e..bdd616dfbb 100644 --- a/posix/regcomp.c +++ b/posix/regcomp.c @@ -566,6 +566,23 @@ weak_alias (__regerror, regerror) #endif +#ifdef RE_ENABLE_I18N +/* This static array is used for the map to single-byte characters when + UTF-8 is used. Otherwise we would allocate memory just to initialize + it the same all the time. UTF-8 is the preferred encoding so this is + a worthwhile optimization. */ +static const bitset utf8_sb_map = +{ + /* Set the first 128 bits. */ +# if UINT_MAX == 0xffffffff + 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff +# else +# error "Add case for new unsigned int size" +# endif +}; +#endif + + static void free_dfa_content (re_dfa_t *dfa) { @@ -613,7 +630,8 @@ free_dfa_content (re_dfa_t *dfa) } re_free (dfa->state_table); #ifdef RE_ENABLE_I18N - re_free (dfa->sb_char); + if (dfa->sb_char != utf8_sb_map) + re_free (dfa->sb_char); #endif #ifdef DEBUG re_free (dfa->re_str); @@ -824,6 +842,9 @@ init_dfa (dfa, pat_len) int pat_len; { int table_size; +#ifndef _LIBC + char *codeset_name; +#endif memset (dfa, '\0', sizeof (re_dfa_t)); @@ -853,22 +874,59 @@ init_dfa (dfa, pat_len) dfa->is_utf8 = 1; dfa->map_notascii = (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_MAP_TO_NONASCII) != 0); +#else +# ifdef HAVE_LANGINFO_CODESET + codeset_name = nl_langinfo (CODESET); +# else + codeset_name = getenv ("LC_ALL"); + if (codeset_name == NULL || codeset[0] == '\0') + codeset_name = getenv ("LC_CTYPE"); + if (codeset_name == NULL || codeset[0] == '\0') + codeset_name = getenv ("LANG"); + if (codeset_name == NULL) + codeset_name = ""; + else if (strchr (codeset_name, '.') != NULL) + codeset_name = strchr (codeset_name, '.') + 1; +# endif + + if (strcasecmp (codeset_name, "UTF-8") == 0 + || strcasecmp (codeset_name, "UTF8") == 0) + dfa->is_utf8 = 1; + + /* We check exhaustively in the loop below if this charset is a + superset of ASCII. */ + dfa->map_notascii = 0; #endif + #ifdef RE_ENABLE_I18N if (dfa->mb_cur_max > 1) { - int i, j, ch; - - dfa->sb_char = (re_bitset_ptr_t) calloc (sizeof (bitset), 1); - if (BE (dfa->sb_char == NULL, 0)) - return REG_ESPACE; if (dfa->is_utf8) - memset (dfa->sb_char, 255, sizeof (unsigned int) * BITSET_UINTS / 2); + dfa->sb_char = (re_bitset_ptr_t) utf8_sb_map; else - for (i = 0, ch = 0; i < BITSET_UINTS; ++i) - for (j = 0; j < UINT_BITS; ++j, ++ch) - if (__btowc (ch) != WEOF) - dfa->sb_char[i] |= 1 << j; + { + int i, j, ch; + + dfa->sb_char = (re_bitset_ptr_t) calloc (sizeof (bitset), 1); + if (BE (dfa->sb_char == NULL, 0)) + return REG_ESPACE; + + /* Clear all bits by, then set those corresponding to single + byte chars. */ + bitset_empty (dfa->sb_char); + + for (i = 0, ch = 0; i < BITSET_UINTS; ++i) + for (j = 0; j < UINT_BITS; ++j, ++ch) + { + wchar_t wch = __btowc (ch); + if (wch != WEOF) + dfa->sb_char[i] |= 1 << j; +# ifndef _LIBC + if (isascii (ch) && wch != (wchar_t) ch) + dfa->map_notascii = 1; +# endif + } + } } #endif diff --git a/posix/regex_internal.c b/posix/regex_internal.c index 96f113745f..609719f79c 100644 --- a/posix/regex_internal.c +++ b/posix/regex_internal.c @@ -293,9 +293,8 @@ build_wcs_upper_buffer (pstr) byte_idx = pstr->valid_len; end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; -#ifdef _LIBC - /* The following optimization assumes that the wchar_t encoding is - always ISO 10646. */ + /* The following optimization assumes that ASCII characters can be + mapped to wide characters with a simple cast. */ if (! pstr->map_notascii && pstr->trans == NULL && !pstr->offsets_needed) { while (byte_idx < end_idx) @@ -309,8 +308,7 @@ build_wcs_upper_buffer (pstr) pstr->mbs[byte_idx] = toupper (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]); /* The next step uses the assumption that wchar_t is encoded - with ISO 10646: all ASCII values can be converted like - this. */ + ASCII-safe: all ASCII values can be converted like this. */ pstr->wcs[byte_idx] = (wchar_t) pstr->mbs[byte_idx]; ++byte_idx; continue; @@ -368,14 +366,11 @@ build_wcs_upper_buffer (pstr) return REG_NOERROR; } else -#endif for (src_idx = pstr->valid_raw_len; byte_idx < end_idx;) { wchar_t wc; const char *p; -#ifdef _LIBC -offsets_needed: -#endif + offsets_needed: remain_len = end_idx - byte_idx; prev_st = pstr->cur_state; if (BE (pstr->trans != NULL, 0)) @@ -647,7 +642,6 @@ re_string_reconstruct (pstr, idx, eflags) int wcs_idx; wint_t wc = WEOF; -#ifdef _LIBC if (pstr->is_utf8) { const unsigned char *raw, *p, *q, *end; @@ -687,7 +681,7 @@ re_string_reconstruct (pstr, idx, eflags) break; } } -#endif + if (wc == WEOF) pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx; if (BE (pstr->valid_len, 0)) diff --git a/posix/regex_internal.h b/posix/regex_internal.h index e807173372..023056c028 100644 --- a/posix/regex_internal.h +++ b/posix/regex_internal.h @@ -27,6 +27,9 @@ #include <stdlib.h> #include <string.h> +#if defined HAVE_LANGINFO_H || defined HAVE_LANGINFO_CODESET || defined _LIBC +# include <langinfo.h> +#endif #if defined HAVE_LOCALE_H || defined _LIBC # include <locale.h> #endif @@ -545,6 +548,9 @@ struct re_backref_cache_entry int str_idx; int subexp_from; int subexp_to; + /* We need only one byte from the following field. If other small + fields are added the type could be changed to 'char'. */ + int more; }; typedef struct diff --git a/posix/regexec.c b/posix/regexec.c index 63436d19eb..72ae70b916 100644 --- a/posix/regexec.c +++ b/posix/regexec.c @@ -93,6 +93,9 @@ static int sift_states_iter_mb (const re_match_context_t *mctx, #endif /* RE_ENABLE_I18N */ static reg_errcode_t sift_states_backward (re_match_context_t *mctx, re_sift_context_t *sctx) internal_function; +static reg_errcode_t build_sifted_states (re_match_context_t *mctx, + re_sift_context_t *sctx, int str_idx, + re_node_set *cur_dest) internal_function; static reg_errcode_t update_cur_sifted_state (re_match_context_t *mctx, re_sift_context_t *sctx, int str_idx, @@ -106,9 +109,13 @@ static reg_errcode_t sub_epsilon_src_nodes (re_dfa_t *dfa, int node, static int check_dst_limits (re_match_context_t *mctx, re_node_set *limits, int dst_node, int dst_idx, int src_node, int src_idx) internal_function; +static int check_dst_limits_calc_pos_1 (re_match_context_t *mctx, + int boundaries, int subexp_idx, + int from_node, int bkref_idx) internal_function; static int check_dst_limits_calc_pos (re_match_context_t *mctx, - int limit, re_node_set *eclosures, - int subexp_idx, int node, int str_idx) internal_function; + int limit, int subexp_idx, + int node, int str_idx, + int bkref_idx) internal_function; static reg_errcode_t check_subexp_limits (re_dfa_t *dfa, re_node_set *dest_nodes, const re_node_set *candidates, @@ -576,8 +583,6 @@ re_exec (s) } #endif /* _REGEX_RE_COMP */ -static re_node_set empty_set; - /* Internal entry point. */ /* Searches for a compiled pattern PREG in the string STRING, whose @@ -640,8 +645,6 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch, start = range = 0; } - re_node_set_init_empty (&empty_set); - /* We must check the longest matching, if nmatch > 0. */ fl_longest_match = (nmatch != 0 || dfa->nbackref); @@ -1492,17 +1495,14 @@ sift_states_backward (mctx, sctx) re_match_context_t *mctx; re_sift_context_t *sctx; { - re_dfa_t *const dfa = mctx->dfa; reg_errcode_t err; int null_cnt = 0; int str_idx = sctx->last_str_idx; re_node_set cur_dest; - re_node_set *cur_src; /* Points the state_log[str_idx]->nodes */ #ifdef DEBUG assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL); #endif - cur_src = &mctx->state_log[str_idx]->nodes; /* Build sifted state_log[str_idx]. It has the nodes which can epsilon transit to the last_node and the last_node itself. */ @@ -1516,7 +1516,6 @@ sift_states_backward (mctx, sctx) /* Then check each states in the state_log. */ while (str_idx > 0) { - int i, ret; /* Update counters. */ null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0; if (null_cnt > mctx->max_mb_elem_len) @@ -1528,56 +1527,12 @@ sift_states_backward (mctx, sctx) } re_node_set_empty (&cur_dest); --str_idx; - cur_src = ((mctx->state_log[str_idx] == NULL) ? &empty_set - : &mctx->state_log[str_idx]->nodes); - - /* Then build the next sifted state. - We build the next sifted state on `cur_dest', and update - `sifted_states[str_idx]' with `cur_dest'. - Note: - `cur_dest' is the sifted state from `state_log[str_idx + 1]'. - `cur_src' points the node_set of the old `state_log[str_idx]'. */ - for (i = 0; i < cur_src->nelem; i++) - { - int prev_node = cur_src->elems[i]; - int naccepted = 0; - re_token_type_t type = dfa->nodes[prev_node].type; - - if (IS_EPSILON_NODE (type)) - continue; -#ifdef RE_ENABLE_I18N - /* If the node may accept `multi byte'. */ - if (ACCEPT_MB_NODE (type)) - naccepted = sift_states_iter_mb (mctx, sctx, prev_node, - str_idx, sctx->last_str_idx); - -#endif /* RE_ENABLE_I18N */ - /* We don't check backreferences here. - See update_cur_sifted_state(). */ - - if (!naccepted - && check_node_accept (mctx, dfa->nodes + prev_node, str_idx) - && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1], - dfa->nexts[prev_node])) - naccepted = 1; - if (naccepted == 0) - continue; - - if (sctx->limits.nelem) - { - int to_idx = str_idx + naccepted; - if (check_dst_limits (mctx, &sctx->limits, - dfa->nexts[prev_node], to_idx, - prev_node, str_idx)) - continue; - } - ret = re_node_set_insert (&cur_dest, prev_node); - if (BE (ret == -1, 0)) - { - err = REG_ESPACE; - goto free_return; - } + if (mctx->state_log[str_idx]) + { + err = build_sifted_states (mctx, sctx, str_idx, &cur_dest); + if (BE (err != REG_NOERROR, 0)) + goto free_return; } /* Add all the nodes which satisfy the following conditions: @@ -1594,6 +1549,66 @@ sift_states_backward (mctx, sctx) return err; } +static reg_errcode_t +build_sifted_states (mctx, sctx, str_idx, cur_dest) + re_match_context_t *mctx; + re_sift_context_t *sctx; + int str_idx; + re_node_set *cur_dest; +{ + re_dfa_t *const dfa = mctx->dfa; + re_node_set *cur_src = &mctx->state_log[str_idx]->nodes; + int i; + + /* Then build the next sifted state. + We build the next sifted state on `cur_dest', and update + `sifted_states[str_idx]' with `cur_dest'. + Note: + `cur_dest' is the sifted state from `state_log[str_idx + 1]'. + `cur_src' points the node_set of the old `state_log[str_idx]'. */ + for (i = 0; i < cur_src->nelem; i++) + { + int prev_node = cur_src->elems[i]; + int naccepted = 0; + re_token_type_t type = dfa->nodes[prev_node].type; + int ret; + + if (IS_EPSILON_NODE (type)) + continue; +#ifdef RE_ENABLE_I18N + /* If the node may accept `multi byte'. */ + if (ACCEPT_MB_NODE (type)) + naccepted = sift_states_iter_mb (mctx, sctx, prev_node, + str_idx, sctx->last_str_idx); +#endif /* RE_ENABLE_I18N */ + + /* We don't check backreferences here. + See update_cur_sifted_state(). */ + if (!naccepted + && check_node_accept (mctx, dfa->nodes + prev_node, str_idx) + && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1], + dfa->nexts[prev_node])) + naccepted = 1; + + if (naccepted == 0) + continue; + + if (sctx->limits.nelem) + { + int to_idx = str_idx + naccepted; + if (check_dst_limits (mctx, &sctx->limits, + dfa->nexts[prev_node], to_idx, + prev_node, str_idx)) + continue; + } + ret = re_node_set_insert (cur_dest, prev_node); + if (BE (ret == -1, 0)) + return REG_ESPACE; + } + + return REG_NOERROR; +} + /* Helper functions. */ static reg_errcode_t @@ -1661,34 +1676,37 @@ update_cur_sifted_state (mctx, sctx, str_idx, dest_nodes) re_dfa_t *const dfa = mctx->dfa; reg_errcode_t err; const re_node_set *candidates; - candidates = ((mctx->state_log[str_idx] == NULL) ? &empty_set + candidates = ((mctx->state_log[str_idx] == NULL) ? NULL : &mctx->state_log[str_idx]->nodes); - /* At first, add the nodes which can epsilon transit to a node in - DEST_NODE. */ - if (dest_nodes->nelem) + if (dest_nodes->nelem == 0) + sctx->sifted_states[str_idx] = NULL; + else { - err = add_epsilon_src_nodes (dfa, dest_nodes, candidates); - if (BE (err != REG_NOERROR, 0)) - return err; - } + if (candidates) + { + /* At first, add the nodes which can epsilon transit to a node in + DEST_NODE. */ + err = add_epsilon_src_nodes (dfa, dest_nodes, candidates); + if (BE (err != REG_NOERROR, 0)) + return err; - /* Then, check the limitations in the current sift_context. */ - if (dest_nodes->nelem && sctx->limits.nelem) - { - err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits, - mctx->bkref_ents, str_idx); + /* Then, check the limitations in the current sift_context. */ + if (sctx->limits.nelem) + { + err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits, + mctx->bkref_ents, str_idx); + if (BE (err != REG_NOERROR, 0)) + return err; + } + } + + sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes); if (BE (err != REG_NOERROR, 0)) return err; } - /* Update state_log. */ - sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes); - if (BE (sctx->sifted_states[str_idx] == NULL && err != REG_NOERROR, 0)) - return err; - - if ((mctx->state_log[str_idx] != NULL - && mctx->state_log[str_idx]->has_backref)) + if (candidates && mctx->state_log[str_idx]->has_backref) { err = sift_states_bkref (mctx, sctx, str_idx, candidates); if (BE (err != REG_NOERROR, 0)) @@ -1785,6 +1803,8 @@ check_dst_limits (mctx, limits, dst_node, dst_idx, src_node, src_idx) re_dfa_t *const dfa = mctx->dfa; int lim_idx, src_pos, dst_pos; + int dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx); + int src_bkref_idx = search_cur_bkref_entry (mctx, src_idx); for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx) { int subexp_idx; @@ -1793,11 +1813,11 @@ check_dst_limits (mctx, limits, dst_node, dst_idx, src_node, src_idx) subexp_idx = dfa->nodes[ent->node].opr.idx - 1; dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx], - dfa->eclosures + dst_node, - subexp_idx, dst_node, dst_idx); + subexp_idx, dst_node, dst_idx, + dst_bkref_idx); src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx], - dfa->eclosures + src_node, - subexp_idx, src_node, src_idx); + subexp_idx, src_node, src_idx, + src_bkref_idx); /* In case of: <src> <dst> ( <subexp> ) @@ -1812,27 +1832,14 @@ check_dst_limits (mctx, limits, dst_node, dst_idx, src_node, src_idx) } static int -check_dst_limits_calc_pos (mctx, limit, eclosures, subexp_idx, from_node, - str_idx) +check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, from_node, bkref_idx) re_match_context_t *mctx; - re_node_set *eclosures; - int limit, subexp_idx, from_node, str_idx; + int boundaries, subexp_idx, from_node, bkref_idx; { re_dfa_t *const dfa = mctx->dfa; - struct re_backref_cache_entry *lim = mctx->bkref_ents + limit; + re_node_set *eclosures = dfa->eclosures + from_node; int node_idx; - /* If we are outside the range of the subexpression, return -1 or 1. */ - if (str_idx < lim->subexp_from) - return -1; - - if (lim->subexp_to < str_idx) - return 1; - - /* If we are within the subexpression, return 0. */ - if (str_idx != lim->subexp_from && str_idx != lim->subexp_to) - return 0; - /* Else, we are on the boundary: examine the nodes on the epsilon closure. */ for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx) @@ -1842,17 +1849,11 @@ check_dst_limits_calc_pos (mctx, limit, eclosures, subexp_idx, from_node, { case OP_BACK_REF: { - int bi = search_cur_bkref_entry (mctx, str_idx); - for (; bi < mctx->nbkref_ents; ++bi) + struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx; + do { - struct re_backref_cache_entry *ent = mctx->bkref_ents + bi; int dst, cpos; - /* If this backreference goes beyond the point we're - examining, don't go any further. */ - if (ent->str_idx > str_idx) - break; - if (ent->node != node || ent->subexp_from != ent->subexp_to) continue; @@ -1865,33 +1866,32 @@ check_dst_limits_calc_pos (mctx, limit, eclosures, subexp_idx, from_node, dst = dfa->edests[node].elems[0]; if (dst == from_node) { - if (str_idx == lim->subexp_from) + if (boundaries & 1) return -1; - else /* if (str_idx == lim->subexp_to) */ + else /* if (boundaries & 2) */ return 0; } - cpos = check_dst_limits_calc_pos (mctx, limit, - dfa->eclosures + dst, - subexp_idx, dst, - str_idx); + cpos = check_dst_limits_calc_pos_1 (mctx, boundaries, + subexp_idx, dst, bkref_idx); - if (cpos == -1 && str_idx == lim->subexp_from) + if (cpos == -1 && (boundaries & 1)) return -1; - if (cpos == 0 /* && str_idx == lim->lim->subexp_to */) + if (cpos == 0 /* && (boundaries & 2) */) return 0; } - break; - } + while (ent++->more); + break; + } case OP_OPEN_SUBEXP: - if (str_idx == lim->subexp_from && subexp_idx == dfa->nodes[node].opr.idx) + if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx) return -1; break; case OP_CLOSE_SUBEXP: - if (str_idx == lim->subexp_to && subexp_idx == dfa->nodes[node].opr.idx) + if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx) return 0; break; @@ -1900,10 +1900,33 @@ check_dst_limits_calc_pos (mctx, limit, eclosures, subexp_idx, from_node, } } - if (str_idx == lim->subexp_to) + return (boundaries & 2) ? 1 : 0; +} + +static int +check_dst_limits_calc_pos (mctx, limit, subexp_idx, from_node, str_idx, bkref_idx) + re_match_context_t *mctx; + int limit, subexp_idx, from_node, str_idx, bkref_idx; +{ + struct re_backref_cache_entry *lim = mctx->bkref_ents + limit; + int boundaries; + + /* If we are outside the range of the subexpression, return -1 or 1. */ + if (str_idx < lim->subexp_from) + return -1; + + if (lim->subexp_to < str_idx) return 1; - else + + /* If we are within the subexpression, return 0. */ + boundaries = (str_idx == lim->subexp_from); + boundaries |= (str_idx == lim->subexp_to) << 1; + if (boundaries == 0) return 0; + + /* Else, examine epsilon closure. */ + return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, + from_node, bkref_idx); } /* Check the limitations of sub expressions LIMITS, and remove the nodes @@ -2015,75 +2038,81 @@ sift_states_bkref (mctx, sctx, str_idx, candidates) reg_errcode_t err; int node_idx, node; re_sift_context_t local_sctx; + int first_idx = search_cur_bkref_entry (mctx, str_idx); + + if (first_idx == -1) + return REG_NOERROR; + local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */ for (node_idx = 0; node_idx < candidates->nelem; ++node_idx) { + int enabled_idx; re_token_type_t type; + struct re_backref_cache_entry *entry; node = candidates->elems[node_idx]; type = dfa->nodes[node].type; /* Avoid infinite loop for the REs like "()\1+". */ if (node == sctx->last_node && str_idx == sctx->last_str_idx) continue; - if (type == OP_BACK_REF) + if (type != OP_BACK_REF) + continue; + + entry = mctx->bkref_ents + first_idx; + enabled_idx = first_idx; + do { - int enabled_idx = search_cur_bkref_entry (mctx, str_idx); - for (; enabled_idx < mctx->nbkref_ents; ++enabled_idx) + int subexp_len, to_idx, dst_node; + re_dfastate_t *cur_state; + + if (entry->node != node) + continue; + subexp_len = entry->subexp_to - entry->subexp_from; + to_idx = str_idx + subexp_len; + dst_node = (subexp_len ? dfa->nexts[node] + : dfa->edests[node].elems[0]); + + if (to_idx > sctx->last_str_idx + || sctx->sifted_states[to_idx] == NULL + || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node) + || check_dst_limits (mctx, &sctx->limits, node, + str_idx, dst_node, to_idx)) + continue; + + if (local_sctx.sifted_states == NULL) { - int subexp_len, to_idx, dst_node; - struct re_backref_cache_entry *entry; - entry = mctx->bkref_ents + enabled_idx; - if (entry->str_idx > str_idx) - break; - if (entry->node != node) - continue; - subexp_len = entry->subexp_to - entry->subexp_from; - to_idx = str_idx + subexp_len; - dst_node = (subexp_len ? dfa->nexts[node] - : dfa->edests[node].elems[0]); - - if (to_idx > sctx->last_str_idx - || sctx->sifted_states[to_idx] == NULL - || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], - dst_node) - || check_dst_limits (mctx, &sctx->limits, node, - str_idx, dst_node, to_idx)) - continue; - { - re_dfastate_t *cur_state; - if (local_sctx.sifted_states == NULL) - { - local_sctx = *sctx; - err = re_node_set_init_copy (&local_sctx.limits, - &sctx->limits); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - } - local_sctx.last_node = node; - local_sctx.last_str_idx = str_idx; - err = re_node_set_insert (&local_sctx.limits, enabled_idx); - if (BE (err < 0, 0)) - { - err = REG_ESPACE; - goto free_return; - } - cur_state = local_sctx.sifted_states[str_idx]; - err = sift_states_backward (mctx, &local_sctx); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - if (sctx->limited_states != NULL) - { - err = merge_state_array (dfa, sctx->limited_states, - local_sctx.sifted_states, - str_idx + 1); - if (BE (err != REG_NOERROR, 0)) - goto free_return; - } - local_sctx.sifted_states[str_idx] = cur_state; - re_node_set_remove (&local_sctx.limits, enabled_idx); - } + local_sctx = *sctx; + err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + } + local_sctx.last_node = node; + local_sctx.last_str_idx = str_idx; + err = re_node_set_insert (&local_sctx.limits, enabled_idx); + if (BE (err < 0, 0)) + { + err = REG_ESPACE; + goto free_return; } + cur_state = local_sctx.sifted_states[str_idx]; + err = sift_states_backward (mctx, &local_sctx); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + if (sctx->limited_states != NULL) + { + err = merge_state_array (dfa, sctx->limited_states, + local_sctx.sifted_states, + str_idx + 1); + if (BE (err != REG_NOERROR, 0)) + goto free_return; + } + local_sctx.sifted_states[str_idx] = cur_state; + re_node_set_remove (&local_sctx.limits, enabled_idx); + + /* mctx->bkref_ents may have changed, reload the pointer. */ + entry = mctx->bkref_ents + enabled_idx; } + while (enabled_idx++, entry++->more); } err = REG_NOERROR; free_return: @@ -2577,15 +2606,15 @@ get_subexp (mctx, bkref_node, bkref_str_idx) const char *buf = (const char *) re_string_get_buffer (&mctx->input); /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */ int cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx); - for (; cache_idx < mctx->nbkref_ents; ++cache_idx) + if (cache_idx != -1) { - const struct re_backref_cache_entry *entry - = &mctx->bkref_ents[cache_idx]; - if (entry->str_idx > bkref_str_idx) - break; - if (entry->node == bkref_node) - return REG_NOERROR; /* We already checked it. */ + const struct re_backref_cache_entry *entry = mctx->bkref_ents + cache_idx; + do + if (entry->node == bkref_node) + return REG_NOERROR; /* We already checked it. */ + while (entry++->more); } + subexp_num = dfa->nodes[bkref_node].opr.idx - 1; /* For each sub expression */ @@ -3115,16 +3144,18 @@ expand_bkref_cache (mctx, cur_nodes, cur_str, subexp_num, { re_dfa_t *const dfa = mctx->dfa; reg_errcode_t err; - int cache_idx, cache_idx_start; - /* The current state. */ + int cache_idx_start = search_cur_bkref_entry (mctx, cur_str); + struct re_backref_cache_entry *ent; - cache_idx_start = search_cur_bkref_entry (mctx, cur_str); - for (cache_idx = cache_idx_start; cache_idx < mctx->nbkref_ents; ++cache_idx) + if (cache_idx_start == -1) + return REG_NOERROR; + + restart: + ent = mctx->bkref_ents + cache_idx_start; + do { int to_idx, next_node; - struct re_backref_cache_entry *ent = mctx->bkref_ents + cache_idx; - if (ent->str_idx > cur_str) - break; + /* Is this entry ENT is appropriate? */ if (!re_node_set_contains (cur_nodes, ent->node)) continue; /* No. */ @@ -3153,8 +3184,7 @@ expand_bkref_cache (mctx, cur_nodes, cur_str, subexp_num, return err; } /* TODO: It is still inefficient... */ - cache_idx = cache_idx_start - 1; - continue; + goto restart; } else { @@ -3189,6 +3219,7 @@ expand_bkref_cache (mctx, cur_nodes, cur_str, subexp_num, return err; } } + while (ent++->more); return REG_NOERROR; } @@ -4115,25 +4146,30 @@ match_ctx_add_entry (mctx, node, str_idx, from, to) sizeof (struct re_backref_cache_entry) * mctx->abkref_ents); mctx->abkref_ents *= 2; } + if (mctx->nbkref_ents > 0 + && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx) + mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1; + mctx->bkref_ents[mctx->nbkref_ents].node = node; mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx; mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from; - mctx->bkref_ents[mctx->nbkref_ents++].subexp_to = to; + mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to; + mctx->bkref_ents[mctx->nbkref_ents++].more = 0; if (mctx->max_mb_elem_len < to - from) mctx->max_mb_elem_len = to - from; return REG_NOERROR; } -/* Search for the first entry which has the same str_idx. - Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */ +/* Search for the first entry which has the same str_idx, or -1 if none is + found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */ static int search_cur_bkref_entry (mctx, str_idx) re_match_context_t *mctx; int str_idx; { - int left, right, mid; - right = mctx->nbkref_ents; + int left, right, mid, last; + last = right = mctx->nbkref_ents; for (left = 0; left < right;) { mid = (left + right) / 2; @@ -4142,7 +4178,10 @@ search_cur_bkref_entry (mctx, str_idx) else right = mid; } - return left; + if (left < last && mctx->bkref_ents[left].str_idx == str_idx) + return left; + else + return -1; } /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches |