Implement loop for global regexps in regexp assembler.

src/runtime.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 3777 matching lines @@
     SetLastMatchInfoNoCaptures(subject,
                                last_match_info,
                                match_pos,
                                match_pos + pattern->length());
     return true;
   }
   return false;  // No matches at all.
 }
 
 
-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,
     Handle<JSArray> last_match_array,
     FixedArrayBuilder* builder) {
   ASSERT(subject->IsFlat());
   int match_start = -1;
   int match_end = 0;
   int pos = 0;
   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);
+    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;
       }
-      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 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;
     } else {
       ASSERT_EQ(result, RegExpImpl::RE_EXCEPTION);
       return result;
     }
-    first = false;
   }
 
   if (match_start >= 0) {
     if (match_end < subject_length) {
       ReplacementStringBuilder::AddSubjectSlice(builder,
                                                 match_end,
                                                 subject_length);
     }
     SetLastMatchInfoNoCaptures(subject,
                                last_match_array,
                                match_start,
                                match_end);
     return RegExpImpl::RE_SUCCESS;
   } else {
     return RegExpImpl::RE_FAILURE;  // No matches at all.
   }
 }
 
 
 // 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,
     Handle<JSArray> last_match_array,
     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();
 
   // Position to search from.
   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);
+      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);
+        }
+        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 {
+              ASSERT(current_result_set[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));
+        }
       }
-      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);
-        }
-        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);
-            } else {
-              substring = isolate->factory()->NewSubString(subject, start, end);
-            }
-            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));
-      }
+      // 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 {
         pos = match_end + 1;
         if (pos > subject_length) {
           break;
         }
       }
 
       result = RegExpImpl::IrregexpExecOnce(regexp,
                                             subject,
                                             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.
       if (match_end < subject_length) {
         ReplacementStringBuilder::AddSubjectSlice(builder,
                                                   match_end,
                                                   subject_length);
       }
 
       int last_match_capture_count = (capture_count + 1) * 2;
@@ skipping 47 matching lines @@
     ASSERT(pattern->IsFlat());
     if (SearchStringMultiple(isolate, subject, pattern,
                              last_match_info, &builder)) {
       return *builder.ToJSArray(result_array);
     }
     return isolate->heap()->null_value();
   }
 
   ASSERT_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);
 
-  RegExpImpl::IrregexpResult result;
+  int result;
   if (regexp->CaptureCount() == 0) {
     result = SearchRegExpNoCaptureMultiple(isolate,
                                            subject,
                                            regexp,
                                            last_match_info,
                                            &builder);
   } else {
     result = SearchRegExpMultiple(isolate,
                                   subject,
                                   regexp,
                                   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();
 }
 
 
 RUNTIME_FUNCTION(MaybeObject*, Runtime_NumberToRadixString) {
   NoHandleAllocation ha;
   ASSERT(args.length() == 2);
   CONVERT_SMI_ARG_CHECKED(radix, 1);
@@ skipping 9442 matching lines @@
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     isolate->counters()->gc_last_resort_from_js()->Increment();
     isolate->heap()->CollectAllGarbage(Heap::kNoGCFlags,
                                        "Runtime::PerformGC");
   }
 }
 
 
 } }  // namespace v8::internal