Implement loop for global regexps in regexp assembler.

src/runtime.cc

Index: src/runtime.cc
diff --git a/src/runtime.cc b/src/runtime.cc
index 0b80effbf21e86138f7e66ea6290998d3922b7de..d2f73f0c445cdad076fe013d8c3d1cfe7c6a0d02 100644
--- a/src/runtime.cc
+++ b/src/runtime.cc
@@ -3795,7 +3795,7 @@ static bool SearchStringMultiple(Isolate* isolate,
 }
 
 
-static RegExpImpl::IrregexpResult SearchRegExpNoCaptureMultiple(
+static int SearchRegExpNoCaptureMultiple(

[Erik Corry, 2012/05/11 11:01:00]

I wonder if we can unify this and SearchRegExpMultiple without a performance
hit.

[Yang, 2012/05/16 14:58:47]

I'll try this in another CL.

     Isolate* isolate,
     Handle<String> subject,
     Handle<JSRegExp> regexp,
@@ -3808,41 +3808,53 @@ static RegExpImpl::IrregexpResult SearchRegExpNoCaptureMultiple(
   int required_registers = RegExpImpl::IrregexpPrepare(regexp, subject);
   if (required_registers < 0) return RegExpImpl::RE_EXCEPTION;
 
-  OffsetsVector registers(required_registers, isolate);
+  OffsetsVector registers(OffsetsVector::kStaticOffsetsVectorSize, isolate);
+  static const int max_result_sets =
+      OffsetsVector::kStaticOffsetsVectorSize / 2;
   Vector<int32_t> register_vector(registers.vector(), registers.length());
   int subject_length = subject->length();
   bool first = true;
-
   for (;;) {  // Break on failure, return on exception.
-    RegExpImpl::IrregexpResult result =
+    int result =

[Erik Corry, 2012/05/11 11:01:00]

How about giving this variable a name like number_of_matches, and getting rid of
RE_SUCCESS and RE_FAILURE.  Just comparing == 0 and > 0 makes sense if the
variable has the right name.

[Yang, 2012/05/16 14:58:47]

Done.

         RegExpImpl::IrregexpExecOnce(regexp,
                                      subject,
                                      pos,
                                      register_vector);
-    if (result == RegExpImpl::RE_SUCCESS) {
-      match_start = register_vector[0];
-      builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
-      if (match_end < match_start) {
-        ReplacementStringBuilder::AddSubjectSlice(builder,
-                                                  match_end,
-                                                  match_start);
-      }
-      match_end = register_vector[1];
-      HandleScope loop_scope(isolate);
-      if (!first) {
-        builder->Add(*isolate->factory()->NewProperSubString(subject,
-                                                             match_start,
-                                                             match_end));
-      } else {
-        builder->Add(*isolate->factory()->NewSubString(subject,
-                                                       match_start,
-                                                       match_end));
+    if (result >= RegExpImpl::RE_SUCCESS) {
+      for (int result_index = 0; result_index < result; result_index++) {
+        int32_t* current_result_set = &register_vector[result_index * 2];
+        match_start = current_result_set[0];
+        builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
+        if (match_end < match_start) {
+          ReplacementStringBuilder::AddSubjectSlice(builder,
+                                                    match_end,
+                                                    match_start);
+        }
+        match_end = current_result_set[1];
+        HandleScope loop_scope(isolate);
+        if (!first) {
+          builder->Add(*isolate->factory()->NewProperSubString(subject,
+                                                               match_start,
+                                                               match_end));
+        } else {
+          builder->Add(*isolate->factory()->NewSubString(subject,
+                                                         match_start,
+                                                         match_end));
+        }
+        first = false;
       }
+
+      // If we did not get the maximum number of resultsets, we can stop here
+      // since there are no matches left.
+      if (result < max_result_sets) break;
+
       if (match_start != match_end) {

[Erik Corry, 2012/05/11 11:01:00]

I don't see this logic replicated in the regexp-macro-assembler.  This suggests
to me that we are missing good tests for it.

         pos = match_end;
       } else {
         pos = match_end + 1;
-        if (pos > subject_length) break;
+        if (pos > subject_length) {

[Erik Corry, 2012/05/11 11:01:00]

unneeded edit

+          break;
+        }
       }
     } else if (result == RegExpImpl::RE_FAILURE) {
       break;
@@ -3850,7 +3862,6 @@ static RegExpImpl::IrregexpResult SearchRegExpNoCaptureMultiple(
       ASSERT_EQ(result, RegExpImpl::RE_EXCEPTION);
       return result;
     }
-    first = false;
   }
 
   if (match_start >= 0) {
@@ -3872,7 +3883,7 @@ static RegExpImpl::IrregexpResult SearchRegExpNoCaptureMultiple(
 
 // Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain
 // separate last match info.  See comment on that function.
-static RegExpImpl::IrregexpResult SearchRegExpMultiple(
+static int SearchRegExpMultiple(
     Isolate* isolate,
     Handle<String> subject,
     Handle<JSRegExp> regexp,
@@ -3880,17 +3891,19 @@ static RegExpImpl::IrregexpResult SearchRegExpMultiple(
     FixedArrayBuilder* builder) {
 
   ASSERT(subject->IsFlat());
-  int required_registers = RegExpImpl::IrregexpPrepare(regexp, subject);
-  if (required_registers < 0) return RegExpImpl::RE_EXCEPTION;
+  int registers_per_result_set = RegExpImpl::IrregexpPrepare(regexp, subject);
+  if (registers_per_result_set < 0) return RegExpImpl::RE_EXCEPTION;
 
-  OffsetsVector registers(required_registers, isolate);
+  int num_registers = Min(OffsetsVector::kStaticOffsetsVectorSize,
+                          registers_per_result_set);
+  int max_result_sets = num_registers / registers_per_result_set;
+  OffsetsVector registers(OffsetsVector::kStaticOffsetsVectorSize, isolate);
   Vector<int32_t> register_vector(registers.vector(), registers.length());
 
-  RegExpImpl::IrregexpResult result =
-      RegExpImpl::IrregexpExecOnce(regexp,
-                                   subject,
-                                   0,
-                                   register_vector);
+  int result = RegExpImpl::IrregexpExecOnce(regexp,
+                                            subject,
+                                            0,
+                                            register_vector);
 
   int capture_count = regexp->CaptureCount();
   int subject_length = subject->length();
@@ -3899,60 +3912,71 @@ static RegExpImpl::IrregexpResult SearchRegExpMultiple(
   int pos = 0;
   // End of previous match. Differs from pos if match was empty.
   int match_end = 0;
-  if (result == RegExpImpl::RE_SUCCESS) {
+  if (result >= RegExpImpl::RE_SUCCESS) {
     bool first = true;
     do {
-      int match_start = register_vector[0];
-      builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
-      if (match_end < match_start) {
-        ReplacementStringBuilder::AddSubjectSlice(builder,
-                                                  match_end,
-                                                  match_start);
-      }
-      match_end = register_vector[1];
-
-      {
-        // Avoid accumulating new handles inside loop.
-        HandleScope temp_scope(isolate);
-        // Arguments array to replace function is match, captures, index and
-        // subject, i.e., 3 + capture count in total.
-        Handle<FixedArray> elements =
-            isolate->factory()->NewFixedArray(3 + capture_count);
-        Handle<String> match;
-        if (!first) {
-          match = isolate->factory()->NewProperSubString(subject,
-                                                         match_start,
-                                                         match_end);
-        } else {
-          match = isolate->factory()->NewSubString(subject,
-                                                   match_start,
-                                                   match_end);
+      int match_start = 0;
+      for (int result_index = 0; result_index < result; result_index++) {
+        int32_t* current_result_set =
+            &register_vector[result_index * registers_per_result_set];
+        match_start = current_result_set[0];
+        builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
+        if (match_end < match_start) {
+          ReplacementStringBuilder::AddSubjectSlice(builder,
+                                                    match_end,
+                                                    match_start);
         }
-        elements->set(0, *match);
-        for (int i = 1; i <= capture_count; i++) {
-          int start = register_vector[i * 2];
-          if (start >= 0) {
-            int end = register_vector[i * 2 + 1];
-            ASSERT(start <= end);
-            Handle<String> substring;
-            if (!first) {
-              substring = isolate->factory()->NewProperSubString(subject,
-                                                                 start,
-                                                                 end);
+        match_end = current_result_set[1];
+
+        {
+          // Avoid accumulating new handles inside loop.
+          HandleScope temp_scope(isolate);
+          // Arguments array to replace function is match, captures, index and
+          // subject, i.e., 3 + capture count in total.
+          Handle<FixedArray> elements =
+              isolate->factory()->NewFixedArray(3 + capture_count);
+          Handle<String> match;
+          if (!first) {
+            match = isolate->factory()->NewProperSubString(subject,

[Erik Corry, 2012/05/11 11:01:00]

Not sure why we need NewProperSubString here.

[Yang, 2012/05/16 14:58:47]

For every substring save for the first one we know that it's a real substring,
so we can omit the length- and start-check using NewProperSubString.
Unfortunately, this does make a performance difference.

+                                                           match_start,
+                                                           match_end);
+          } else {
+            match = isolate->factory()->NewSubString(subject,
+                                                     match_start,
+                                                     match_end);
+          }
+          elements->set(0, *match);
+          for (int i = 1; i <= capture_count; i++) {

[Erik Corry, 2012/05/11 11:01:00]

I think you could just start this loop at 0 and remove some code duplication.

[Yang, 2012/05/16 14:58:47]

After removing the call to NewSubString here (first is false in any case), I
think it makes sense to have the first loop stand out: we don't do a check for
-1 for undefined there and can be sure not to use NewSubString.

+            int start = current_result_set[i * 2];
+            if (start >= 0) {
+              int end = current_result_set[i * 2 + 1];
+              ASSERT(start <= end);
+              Handle<String> substring;
+              if (!first) {
+                substring = isolate->factory()->NewProperSubString(subject,
+                                                                   start,
+                                                                   end);
+              } else {
+                substring = isolate->factory()->NewSubString(subject,
+                                                             start,
+                                                             end);
+              }
+              elements->set(i, *substring);
             } else {
-              substring = isolate->factory()->NewSubString(subject, start, end);
+              ASSERT(current_result_set[i * 2 + 1] < 0);
+              elements->set(i, isolate->heap()->undefined_value());
             }
-            elements->set(i, *substring);
-          } else {
-            ASSERT(register_vector[i * 2 + 1] < 0);
-            elements->set(i, isolate->heap()->undefined_value());
           }
+          elements->set(capture_count + 1, Smi::FromInt(match_start));
+          elements->set(capture_count + 2, *subject);
+          builder->Add(*isolate->factory()->NewJSArrayWithElements(elements));
         }
-        elements->set(capture_count + 1, Smi::FromInt(match_start));
-        elements->set(capture_count + 2, *subject);
-        builder->Add(*isolate->factory()->NewJSArrayWithElements(elements));
       }
 
+      // If we did not get the maximum number of resultsets, we can stop here
+      // since there are no matches left.
+      if (result < max_result_sets) break;
+
       if (match_end > match_start) {
         pos = match_end;
       } else {
@@ -3967,7 +3991,7 @@ static RegExpImpl::IrregexpResult SearchRegExpMultiple(
                                             pos,
                                             register_vector);
       first = false;
-    } while (result == RegExpImpl::RE_SUCCESS);
+    } while (result >= RegExpImpl::RE_SUCCESS);
 
     if (result != RegExpImpl::RE_EXCEPTION) {
       // Finished matching, with at least one match.
@@ -4035,7 +4059,7 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExecMultiple) {
 
   ASSERT_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);
 
-  RegExpImpl::IrregexpResult result;
+  int result;
   if (regexp->CaptureCount() == 0) {
     result = SearchRegExpNoCaptureMultiple(isolate,
                                            subject,
@@ -4049,7 +4073,7 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExecMultiple) {
                                   last_match_info,
                                   &builder);
   }
-  if (result == RegExpImpl::RE_SUCCESS) return *builder.ToJSArray(result_array);
+  if (result >= RegExpImpl::RE_SUCCESS) return *builder.ToJSArray(result_array);
   if (result == RegExpImpl::RE_FAILURE) return isolate->heap()->null_value();
   ASSERT_EQ(result, RegExpImpl::RE_EXCEPTION);
   return Failure::Exception();