mame	2010-02-17 21:36:41 +0900 (Wed, 17 Feb 2010)

  New Revision: 26701

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=26701

  Log:
    * 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.

  Modified files:
    trunk/ChangeLog
    trunk/regcomp.c
    trunk/test/ruby/test_regexp.rb

Index: regcomp.c
===================================================================
--- regcomp.c	(revision 26700)
+++ regcomp.c	(revision 26701)
@@ -3643,6 +3643,7 @@
 #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 @@
     {
       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 @@
 	}
       }
 #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 @@
     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
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 26700)
+++ ChangeLog	(revision 26701)
@@ -1,3 +1,10 @@
+Wed Feb 17 21:34:01 2010  Yusuke Endoh  <mame@t...>
+
+	* 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.
+
 Wed Feb 17 21:26:53 2010  Tanaka Akira  <akr@f...>
 
 	* bootstraptest/runner.rb (assert_normal_exit): add :timeout option.
Index: test/ruby/test_regexp.rb
===================================================================
--- test/ruby/test_regexp.rb	(revision 26700)
+++ test/ruby/test_regexp.rb	(revision 26701)
@@ -800,4 +800,11 @@
     assert_nothing_raised { eval("a = 1; /\#{ a }/; a") }
     assert_nothing_raised { eval("a = 1; /\#{ a }/o; a") }
   end
+
+  def test_optimize_last_anycharstar
+    s = "1" + " " * 5000000
+    assert_nothing_raised { s.match(/(\d) (.*)/) }
+    assert_equal("1", $1)
+    assert_equal(" " * 4999999, $2)
+  end
 end

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/