summaryrefslogtreecommitdiff
path: root/posix/regexec.c
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2004-11-12 09:45:05 +0000
committerUlrich Drepper <drepper@redhat.com>2004-11-12 09:45:05 +0000
commit7db612081aa9c2d0b7e6205582a80aa2e9342f8f (patch)
treed904731f71b778954e15e6a7ba7bb9dbdf0bc4c9 /posix/regexec.c
parentccd8de9aa69df004a3df02333fb01f4eaf990d92 (diff)
2004-11-12 Ulrich Drepper <drepper@redhat.com> * posix/Makefile (tests): Add bug-regex24. * posix/bug-regex24.c: New file. 2004-11-12 Paolo Bonzini <bonzini@gnu.org> * posix/regexec.c (check_dst_limits_calc_pos_1): Use the map to cut recursive paths. Make exit condition more precise. (match_ctx_add_entry): Initialize the map. * posix/regex_internal.h (struct re_backref_cache_entry): Add a map of reachable subexpression nodes from each backreference cache entry.
Diffstat (limited to 'posix/regexec.c')
-rw-r--r--posix/regexec.c25
1 files changed, 22 insertions, 3 deletions
diff --git a/posix/regexec.c b/posix/regexec.c
index 79104119be..a03df2636a 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -1885,7 +1885,12 @@ check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, from_node, bkref_idx)
{
int dst, cpos;
- if (ent->node != node || ent->subexp_from != ent->subexp_to)
+ if (ent->node != node)
+ continue;
+
+ if (subexp_idx <= 8 * sizeof (ent->eps_reachable_subexps_map)
+ && (ent->eps_reachable_subexps_map
+ & (1 << (subexp_idx - 1))) == 0)
continue;
/* Recurse trying to reach the OP_OPEN_SUBEXP and
@@ -1906,11 +1911,13 @@ check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, from_node, bkref_idx)
cpos = check_dst_limits_calc_pos_1 (mctx, boundaries,
subexp_idx, dst, bkref_idx);
- if (cpos == -1 && (boundaries & 1))
+ if (cpos == -1 /* && (boundaries & 1) */)
return -1;
- if (cpos == 0 /* && (boundaries & 2) */)
+ if (cpos == 0 && (boundaries & 2))
return 0;
+
+ ent->eps_reachable_subexps_map &= ~(1 << (subexp_idx - 1));
}
while (ent++->more);
break;
@@ -4169,6 +4176,18 @@ match_ctx_add_entry (mctx, node, str_idx, from, to)
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;
+
+ /* This is a cache that saves negative results of check_dst_limits_calc_pos.
+ If bit N is clear, means that this entry won't epsilon-transition to
+ an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
+ it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
+ such node.
+
+ A backreference does not epsilon-transition unless it is empty, so set
+ to all zeros if FROM != TO. */
+ mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
+ = (from == to ? ~0 : 0);
+
mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
if (mctx->max_mb_elem_len < to - from)
mctx->max_mb_elem_len = to - from;