Unroll + and ? to reduce loop-related work.

src/jsregexp.cc

Index: src/jsregexp.cc
===================================================================
--- src/jsregexp.cc	(revision 994)
+++ src/jsregexp.cc	(working copy)
@@ -2695,6 +2695,48 @@
   //
   // TODO(someone): clear captures on repetition and handle empty
   //   matches.
+
+  // 15.10.2.5 RepeatMatcher algorithm.
+  // The parser has already eliminated the case where max is 0.  In the case
+  // where max_match is zero the parser has removed the quantifier if min was
+  // > 0 and removed the atom if min was 0.  See AddQuantifierToAtom.
+
+  // If we know that we cannot match zero length then things are a little
+  // simpler since we don't need to make the special zero length match check
+  // from step 2.1.  If the min and max are small we can unroll a little in
+  // this case.
+  if (max == 0) return on_success;  // This can happen due to recursion.
+  if (body->min_match() > 0) {
+    if (min > 0 && min <= 3) {

[Lasse Reichstein, 2008/12/18 12:34:17]

static const int kMaxUnrollRepetition = 3;

+      int new_max = (max == kInfinity) ? max : max - min;
+      // Recurse once to get the loop or optional matches after the fixed ones.
+      RegExpNode* answer =
+          ToNode(0, new_max, is_greedy, body, compiler, on_success);
+      // Unroll the forced matches from 0 to min.  This can cause chains of
+      // TextNodes (which the parser does not generate).

[Lasse Reichstein, 2008/12/18 12:34:17]

Will these chains of text nodes normalied at a later time?

+      for (int i = 0; i < min; i++) {
+        answer = body->ToNode(compiler, answer);
+      }
+      return answer;
+    }
+    if (max <= 3) {

[Lasse Reichstein, 2008/12/18 12:34:17]

Same constant, or another?

+      ASSERT(min == 0);
+      // Unroll the optional matches up to max.
+      RegExpNode* answer = on_success;
+      for (int i = 0; i < max; i++) {
+        ChoiceNode* alternation = new ChoiceNode(2);
+        if (is_greedy) {
+          alternation->AddAlternative(GuardedAlternative(body->ToNode(compiler, answer)));
+          alternation->AddAlternative(GuardedAlternative(on_success));
+        } else {
+          alternation->AddAlternative(GuardedAlternative(on_success));
+          alternation->AddAlternative(GuardedAlternative(body->ToNode(compiler, answer)));
+        }
+        answer = alternation;
+      }
+      return answer;
+    }
+  }
   bool has_min = min > 0;
   bool has_max = max < RegExpTree::kInfinity;
   bool needs_counter = has_min || has_max;