[regexp] Add fast-path for global, callable replace

src/runtime/runtime-regexp.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/runtime/runtime-utils.h"
 
 #include "src/arguments.h"
 #include "src/conversions-inl.h"
 #include "src/isolate-inl.h"
 #include "src/messages.h"
@@ skipping 955 matching lines @@
   virtual ~VectorBackedMatch() {}
 
  private:
   Isolate* isolate_;
   Handle<String> subject_;
   Handle<String> match_;
   const int match_position_;
   ZoneVector<Handle<Object>>* captures_;
 };
 
-// Only called from RegExpExecMultiple so it doesn't need to maintain
+// Only called from Runtime_RegExpExecMultiple so it doesn't need to maintain
 // separate last match info.  See comment on that function.
 template <bool has_capture>
-MaybeHandle<Object> SearchRegExpMultiple(
-    Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp,
-    Handle<RegExpMatchInfo> last_match_array,
-    Handle<FixedArray> result_elements) {
+static Object* SearchRegExpMultiple(Isolate* isolate, Handle<String> subject,
+                                    Handle<JSRegExp> regexp,
+                                    Handle<RegExpMatchInfo> last_match_array,
+                                    Handle<JSArray> result_array) {
   DCHECK(subject->IsFlat());
   DCHECK_NE(has_capture, regexp->CaptureCount() == 0);
 
   int capture_count = regexp->CaptureCount();
   int subject_length = subject->length();
 
   static const int kMinLengthToCache = 0x1000;
 
   if (subject_length > kMinLengthToCache) {
     FixedArray* last_match_cache;
     Object* cached_answer = RegExpResultsCache::Lookup(
         isolate->heap(), *subject, regexp->data(), &last_match_cache,
         RegExpResultsCache::REGEXP_MULTIPLE_INDICES);
     if (cached_answer->IsFixedArray()) {
       int capture_registers = (capture_count + 1) * 2;
       int32_t* last_match = NewArray<int32_t>(capture_registers);
       for (int i = 0; i < capture_registers; i++) {
         last_match[i] = Smi::cast(last_match_cache->get(i))->value();
       }
-      Handle<FixedArray> cached_fixed_array(FixedArray::cast(cached_answer));
+      Handle<FixedArray> cached_fixed_array =
+          Handle<FixedArray>(FixedArray::cast(cached_answer));
+      // The cache FixedArray is a COW-array and we need to return a copy.

[jgruber, 2016/10/19 16:39:13]

It might not make sense anymore for the result cache to store COW arrays, now
that our implementation operates directly on fixed arrays (which ignores any COW
logic).

In principle, we could also move away from JSArray wrappers, but in this case
the StringBuilderConcat runtime function still expects a JSArray. Maybe operate
on FixedArrays here and wrap it in a JSArray shortly before the call to SBC?

[Yang, 2016/10/20 09:53:14]

I'd simply introduce a version of SBC that only takes FixedArrays.

Maybe we can avoid modifying the FixedArray altogether, so that we don't need to
make a copy for caching. Iirc we modify the FixedArray because we call the
function and replace elements by the return values. That whole FixedArray is
then passed to SBC.

Maybe we could have RegExpMultiple return a FixedArray for the regexp results,
which is cacheable. Return values of calling the functions is collected in a
second FixedArray, and SBC can then merge both to the final result. Does that
make sense?

[jgruber, 2016/10/20 10:58:30]

That would work, I'm just not sure what we would gain.

We still need to create an array of the same size (initialized with holes so
O(n)), and then do one write per function result. The same amount of work as
now, but added complexity because of a new SBC that can handle merging.

What about we:
* Move RegExpExecMultiple to take and return FixedArrays.
* Remove the result_array arg and alloc in REExecMultiple as needed.
* Always return copies of the cached FixedArrays.
* Wrap the FixedArray in a JSArray just before the call to SBC. If we need to
optimize, we still have the option of adding a new SBC that takes FixedArrays.

+      Handle<FixedArray> copied_fixed_array =
+          isolate->factory()->CopyFixedArrayWithMap(
+              cached_fixed_array, isolate->factory()->fixed_array_map());
+      JSArray::SetContent(result_array, copied_fixed_array);
       RegExpImpl::SetLastMatchInfo(last_match_array, subject, capture_count,
                                    last_match);
       DeleteArray(last_match);
-      // The cache FixedArray is a COW-array and we need to return a copy.
-      return isolate->factory()->CopyFixedArrayWithMap(
-          cached_fixed_array, isolate->factory()->fixed_array_map());
+      return *result_array;
     }
   }
 
   RegExpImpl::GlobalCache global_cache(regexp, subject, isolate);
-  if (global_cache.HasException()) return MaybeHandle<Object>();
+  if (global_cache.HasException()) return isolate->heap()->exception();
 
   // Ensured in Runtime_RegExpExecMultiple.
+  DCHECK(result_array->HasFastObjectElements());
+  Handle<FixedArray> result_elements(
+      FixedArray::cast(result_array->elements()));
   if (result_elements->length() < 16) {
     result_elements = isolate->factory()->NewFixedArrayWithHoles(16);
   }
 
   FixedArrayBuilder builder(result_elements);
 
   // Position to search from.
   int match_start = -1;
   int match_end = 0;
   bool first = true;
@@ skipping 46 matching lines @@
         }
         elements->set(capture_count + 1, Smi::FromInt(match_start));
         elements->set(capture_count + 2, *subject);
         builder.Add(*isolate->factory()->NewJSArrayWithElements(elements));
       } else {
         builder.Add(*match);
       }
     }
   }
 
-  if (global_cache.HasException()) return MaybeHandle<Object>();
+  if (global_cache.HasException()) return isolate->heap()->exception();
 
   if (match_start >= 0) {
     // Finished matching, with at least one match.
     if (match_end < subject_length) {
       ReplacementStringBuilder::AddSubjectSlice(&builder, match_end,
                                                 subject_length);
     }
 
     RegExpImpl::SetLastMatchInfo(last_match_array, subject, capture_count,
                                  global_cache.LastSuccessfulMatch());
 
-    Handle<FixedArray> result_fixed_array = builder.array();
-    result_fixed_array->Shrink(builder.length());
-
     if (subject_length > kMinLengthToCache) {
       // Store the last successful match into the array for caching.
       // TODO(yangguo): do not expose last match to JS and simplify caching.
       int capture_registers = (capture_count + 1) * 2;
       Handle<FixedArray> last_match_cache =
           isolate->factory()->NewFixedArray(capture_registers);
       int32_t* last_match = global_cache.LastSuccessfulMatch();
       for (int i = 0; i < capture_registers; i++) {
         last_match_cache->set(i, Smi::FromInt(last_match[i]));
       }
-      // Cache the result and turn the FixedArray into a COW array.
+      Handle<FixedArray> result_fixed_array = builder.array();
+      result_fixed_array->Shrink(builder.length());
+      // Cache the result and copy the FixedArray into a COW array.
+      Handle<FixedArray> copied_fixed_array =
+          isolate->factory()->CopyFixedArrayWithMap(
+              result_fixed_array, isolate->factory()->fixed_array_map());
       RegExpResultsCache::Enter(
-          isolate, subject, handle(regexp->data(), isolate), result_fixed_array,
+          isolate, subject, handle(regexp->data(), isolate), copied_fixed_array,
           last_match_cache, RegExpResultsCache::REGEXP_MULTIPLE_INDICES);
     }
-    // The cache FixedArray is a COW-array and we need to return a copy.
-    return isolate->factory()->CopyFixedArrayWithMap(
-        result_fixed_array, isolate->factory()->fixed_array_map());
+    return *builder.ToJSArray(result_array);
   } else {
-    return isolate->factory()->null_value();  // No matches at all.
+    return isolate->heap()->null_value();  // No matches at all.
   }
 }
 
-// This is only called for StringReplaceGlobalRegExpWithFunction.  This sets
-// lastMatchInfoOverride to maintain the last match info, so we don't need to
-// set any other last match array info.
-MaybeHandle<Object> RegExpExecMultiple(Isolate* isolate,
-                                       Handle<JSRegExp> regexp,
-                                       Handle<String> subject,
-                                       Handle<RegExpMatchInfo> last_match_info,
-                                       Handle<FixedArray> result_array) {
-  subject = String::Flatten(subject);
-  CHECK(regexp->GetFlags() & JSRegExp::kGlobal);
-
-  if (regexp->CaptureCount() == 0) {
-    return SearchRegExpMultiple<false>(isolate, subject, regexp,
-                                       last_match_info, result_array);
-  } else {
-    return SearchRegExpMultiple<true>(isolate, subject, regexp, last_match_info,
-                                      result_array);
-  }
-}
-
-// Helper function for replacing regular expressions with the result of a
-// function application in String.prototype.replace.
-MaybeHandle<String> StringReplaceGlobalRegExpWithFunction(
-    Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp,
-    Handle<Object> replace_obj) {
-  Factory* factory = isolate->factory();
-
-  // TODO(jgruber): Convert result_array into a List<Handle<Object>> (or
-  // similar) and adapt / remove FixedArrayBuilder.
-  Handle<RegExpMatchInfo> last_match_info = isolate->regexp_last_match_info();
-  Handle<FixedArray> result_array = factory->NewFixedArrayWithHoles(16);
-
-  Handle<Object> res;
-  ASSIGN_RETURN_ON_EXCEPTION(isolate, res,
-                             RegExpExecMultiple(isolate, regexp, subject,
-                                                last_match_info, result_array),
-                             String);
-
-  // Reload the last match info since it might have changed in the meantime.
-  last_match_info = isolate->regexp_last_match_info();
-
-  if (res->IsNull(isolate)) return subject;  // No matches at all.
-
-  result_array = Handle<FixedArray>::cast(res);
-  const int result_length = result_array->length();
-
-  const int num_captures = last_match_info->NumberOfCaptureRegisters() / 2;
-  if (num_captures == 1) {
-    // If the number of captures is one then there are no explicit captures in
-    // the regexp, just the implicit capture that captures the whole match.  In
-    // this case we can simplify quite a bit and end up with something faster.
-    // The builder will consist of some integers that indicate slices of the
-    // input string and some replacements that were returned from the replace
-    // function.
-    int match_start = 0;
-    for (int i = 0; i < result_length; i++) {
-      Handle<Object> elem = FixedArray::get(*result_array, i, isolate);
-      if (elem->IsSmi()) {
-        // Integers represent slices of the original string.
-        // TODO(jgruber): Maybe we don't need this weird encoding anymore (in
-        // preparation to invoking StringBuilderConcat), but can just copy into
-        // the result string with the IncrementalStringBuilder as we go?
-        const int elem_value = Handle<Smi>::cast(elem)->value();
-        if (elem_value > 0) {
-          match_start = (elem_value >> 11) + (elem_value & 0x7ff);
-        } else {
-          Handle<Object> next_elem =
-              FixedArray::get(*result_array, ++i, isolate);
-          const int next_elem_value = Handle<Smi>::cast(next_elem)->value();
-          match_start = next_elem_value - elem_value;
-        }
-      } else {
-        DCHECK(elem->IsString());
-        Handle<String> elem_string = Handle<String>::cast(elem);
-
-        // Overwrite the i'th element in the results with the string we got
-        // back from the callback function.
-        const int argc = 3;
-        ScopedVector<Handle<Object>> argv(argc);
-
-        argv[0] = elem_string;
-        argv[1] = handle(Smi::FromInt(match_start), isolate);
-        argv[2] = subject;
-
-        Handle<Object> replacement_obj;
-        ASSIGN_RETURN_ON_EXCEPTION(
-            isolate, replacement_obj,
-            Execution::Call(isolate, replace_obj, factory->undefined_value(),
-                            argc, argv.start()),
-            String);
-
-        Handle<String> replacement;
-        ASSIGN_RETURN_ON_EXCEPTION(isolate, replacement,
-                                   Object::ToString(isolate, replacement_obj),
-                                   String);
-
-        result_array->set(i, *replacement);
-        match_start += elem_string->length();
-      }
-    }
-  } else {
-    DCHECK(num_captures > 1);
-    for (int i = 0; i < result_length; i++) {
-      Handle<Object> elem = FixedArray::get(*result_array, i, isolate);
-      if (elem->IsSmi()) continue;
-
-      // TODO(jgruber): We can skip this whole round-trip through a JS array
-      // for result_array.
-      Handle<JSArray> elem_array = Handle<JSArray>::cast(elem);
-      Handle<FixedArray> elem_array_elems(
-          FixedArray::cast(elem_array->elements()), isolate);
-
-      const int argc = elem_array_elems->length();
-      ScopedVector<Handle<Object>> argv(argc);
-
-      for (int j = 0; j < argc; j++) {
-        argv[j] = FixedArray::get(*elem_array_elems, j, isolate);
-      }
-
-      // TODO(jgruber): This call is another pattern we could refactor.
-      Handle<Object> replacement_obj;
-      ASSIGN_RETURN_ON_EXCEPTION(
-          isolate, replacement_obj,
-          Execution::Call(isolate, replace_obj, factory->undefined_value(),
-                          argc, argv.start()),
-          String);
-
-      Handle<String> replacement;
-      ASSIGN_RETURN_ON_EXCEPTION(isolate, replacement,
-                                 Object::ToString(isolate, replacement_obj),
-                                 String);
-
-      result_array->set(i, *replacement);
-    }
-  }
-
-  if (result_length == 0) {
-    return factory->empty_string();
-  } else if (result_length == 1) {
-    Handle<Object> first = FixedArray::get(*result_array, 0, isolate);
-    if (first->IsString()) return Handle<String>::cast(first);
-  }
-
-  bool one_byte = subject->HasOnlyOneByteChars();
-  const int length = StringBuilderConcatLength(subject->length(), *result_array,
-                                               result_length, &one_byte);
-
-  if (length == -1) {
-    isolate->Throw(isolate->heap()->illegal_argument_string());
-    return MaybeHandle<String>();
-  }
-
-  if (one_byte) {
-    Handle<SeqOneByteString> answer;
-    ASSIGN_RETURN_ON_EXCEPTION(isolate, answer,
-                               isolate->factory()->NewRawOneByteString(length),
-                               String);
-    StringBuilderConcatHelper(*subject, answer->GetChars(), *result_array,
-                              result_length);
-    return answer;
-  } else {
-    DCHECK(!one_byte);
-    Handle<SeqTwoByteString> answer;
-    ASSIGN_RETURN_ON_EXCEPTION(isolate, answer,
-                               isolate->factory()->NewRawTwoByteString(length),
-                               String);
-    StringBuilderConcatHelper(*subject, answer->GetChars(), *result_array,
-                              result_length);
-    return answer;
-  }
-
-  UNREACHABLE();
-  return MaybeHandle<String>();
-}
-
 MaybeHandle<String> StringReplaceNonGlobalRegExpWithFunction(
     Isolate* isolate, Handle<String> subject, Handle<JSRegExp> regexp,
     Handle<Object> replace_obj) {
   Factory* factory = isolate->factory();
   Handle<RegExpMatchInfo> last_match_info = isolate->regexp_last_match_info();
 
   // TODO(jgruber): This is a pattern we could refactor.
   Handle<Object> match_indices_obj;
   ASSIGN_RETURN_ON_EXCEPTION(
       isolate, match_indices_obj,
@@ skipping 132 matching lines @@
       Object* result = StringReplaceGlobalRegExpWithString(
           isolate, string, regexp, replace, last_match_info);
       if (result->IsString()) {
         return handle(String::cast(result), isolate);
       } else {
         return MaybeHandle<String>();
       }
     }
   } else {
     DCHECK(functional_replace);
-    if (global) {
-      // Global regexp search, function replace.
-      return StringReplaceGlobalRegExpWithFunction(isolate, string, regexp,
-                                                   replace_obj);
-    } else {
-      // Non-global regexp search, function replace.
-      return StringReplaceNonGlobalRegExpWithFunction(isolate, string, regexp,
-                                                      replace_obj);
-    }
+    DCHECK(!global);  // Handled as fast path.

[jgruber, 2016/10/19 16:39:13]

The entire functional_replace branch should be removed since it is dispatched
directly from the TF impl. We should also use the same map-based fast-path
checks from C++ as in TF.

For replace, we could even dispatch all 'fast' paths (in the sense of unmodified
JSRegExp instances) from TF and only keep the slow path in
Runtime_RegExpReplace.

+    // Non-global regexp search, function replace.
+    return StringReplaceNonGlobalRegExpWithFunction(isolate, string, regexp,
+                                                    replace_obj);
   }
 
   UNREACHABLE();
   return MaybeHandle<String>();
 }
 
 }  // namespace
 
-RUNTIME_FUNCTION(Runtime_StringReplaceGlobalRegExpWithFunction) {
-  HandleScope scope(isolate);
-  DCHECK(args.length() == 3);
+// This is only called for StringReplaceGlobalRegExpWithFunction.
+RUNTIME_FUNCTION(Runtime_RegExpExecMultiple) {
+  HandleScope handles(isolate);
+  DCHECK(args.length() == 4);
 
-  CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
-  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1);
-  CONVERT_ARG_HANDLE_CHECKED(JSObject, replace, 2);
+  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
+  CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
+  CONVERT_ARG_HANDLE_CHECKED(RegExpMatchInfo, last_match_info, 2);
+  CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3);

[jgruber, 2016/10/19 16:39:13]

Reusing the result array does not seem to make any runtime difference for
ss/unpack-code. We could probably remove the result_array arg entirely and just
create it as needed in SearchRegExpMultiple.

[Yang, 2016/10/20 09:53:14]

I wonder whether we need a JSArray for this at all. Can't we just return a
FixedArray directly?

[jgruber, 2016/10/20 10:58:30]

Sure. I kept the JSArray return type for now because of the interaction with
StringBuilderConcat. This is something worth looking at in a follow-up though.

+  CHECK(result_array->HasFastObjectElements());
 
-  RETURN_RESULT_OR_FAILURE(isolate, StringReplaceGlobalRegExpWithFunction(
-                                        isolate, subject, regexp, replace));
+  subject = String::Flatten(subject);
+  CHECK(regexp->GetFlags() & JSRegExp::kGlobal);
+
+  if (regexp->CaptureCount() == 0) {
+    return SearchRegExpMultiple<false>(isolate, subject, regexp,
+                                       last_match_info, result_array);
+  } else {
+    return SearchRegExpMultiple<true>(isolate, subject, regexp, last_match_info,
+                                      result_array);
+  }
 }
 
 RUNTIME_FUNCTION(Runtime_StringReplaceNonGlobalRegExpWithFunction) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 3);
 
   CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1);
   CONVERT_ARG_HANDLE_CHECKED(JSObject, replace, 2);
 
@@ skipping 197 matching lines @@
 
 RUNTIME_FUNCTION(Runtime_IsRegExp) {
   SealHandleScope shs(isolate);
   DCHECK(args.length() == 1);
   CONVERT_ARG_CHECKED(Object, obj, 0);
   return isolate->heap()->ToBoolean(obj->IsJSRegExp());
 }
 
 }  // namespace internal
 }  // namespace v8