summaryrefslogtreecommitdiff
path: root/regcomp.c
diff options
context:
space:
mode:
authormame <mame@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2010-02-17 12:36:41 (GMT)
committermame <mame@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2010-02-17 12:36:41 (GMT)
commit457c2c4a55b5896b30510ff8b39256b61b46cdf4 (patch)
tree2029f3eae8accb28962f50e2e5602f21d32a9512 /regcomp.c
parent24421c835d85bdff2a8878cab1befc3255685b67 (diff)
* regcomp.c (setup_tree, onig_compile): optimize .* at last by
converting into (?>.*), which does not backtrack. [ruby-core:27791] * test/ruby/test_regexp.rb: add a test for above. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@26701 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'regcomp.c')
-rw-r--r--regcomp.c20
1 files changed, 18 insertions, 2 deletions
diff --git a/regcomp.c b/regcomp.c
index e1ac7ee..16c816b 100644
--- a/regcomp.c
+++ b/regcomp.c
@@ -3643,6 +3643,7 @@ setup_comb_exp_check(Node* node, int state, ScanEnv* env)
#define IN_NOT (1<<1)
#define IN_REPEAT (1<<2)
#define IN_VAR_REPEAT (1<<3)
+#define IN_LAST (1<<4)
/* setup_tree does the following work.
1. check empty loop. (set qn->target_empty_info)
@@ -3664,7 +3665,8 @@ setup_tree(Node* node, regex_t* reg, int state, ScanEnv* env)
{
Node* prev = NULL_NODE;
do {
- r = setup_tree(NCAR(node), reg, state, env);
+ int s = IS_NOT_NULL(NCDR(node)) ? (state & ~IN_LAST) : state;
+ r = setup_tree(NCAR(node), reg, s, env);
if (IS_NOT_NULL(prev) && r == 0) {
r = next_setup(prev, NCAR(node), reg);
}
@@ -3795,6 +3797,20 @@ setup_tree(Node* node, regex_t* reg, int state, ScanEnv* env)
}
}
#endif
+
+ if ((state & IN_LAST) != 0 && qn->greedy && IS_REPEAT_INFINITE(qn->upper)) {
+ /* automatic posseivation a* (at last) ==> (?>a*) */
+ if (qn->lower <= 1) {
+ int ttype = NTYPE(qn->target);
+ if (IS_NODE_TYPE_SIMPLE(ttype)) {
+ Node* en = onig_node_new_enclose(ENCLOSE_STOP_BACKTRACK);
+ CHECK_NULL_RETURN_MEMERR(en);
+ SET_ENCLOSE_STATUS(en, NST_STOP_BT_SIMPLE_REPEAT);
+ swap_node(node, en);
+ NENCLOSE(node)->target = en;
+ }
+ }
+ }
}
break;
@@ -5423,7 +5439,7 @@ onig_compile(regex_t* reg, const UChar* pattern, const UChar* pattern_end,
reg->num_call = 0;
#endif
- r = setup_tree(root, reg, 0, &scan_env);
+ r = setup_tree(root, reg, IN_LAST, &scan_env);
if (r != 0) goto err_unset;
#ifdef ONIG_DEBUG_PARSE_TREE