Take advantage of batched results when matching global regexp.

src/jsregexp.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 260 matching lines @@
                                int to) {
   NoHandleAllocation no_handles;
   RegExpImpl::SetLastCaptureCount(array, 2);
   RegExpImpl::SetLastSubject(array, subject);
   RegExpImpl::SetLastInput(array, subject);
   RegExpImpl::SetCapture(array, 0, from);
   RegExpImpl::SetCapture(array, 1, to);
 }
 
 
-Handle<Object> RegExpImpl::AtomExec(Handle<JSRegExp> re,
-                                    Handle<String> subject,
-                                    int index,
-                                    Handle<JSArray> last_match_info) {
-  Isolate* isolate = re->GetIsolate();
+int RegExpImpl::AtomExecRaw(Handle<JSRegExp> regexp,
+                            Handle<String> subject,
+                            int index,
+                            int32_t* output,
+                            int output_size) {
+  Isolate* isolate = regexp->GetIsolate();
 
   ASSERT(0 <= index);
   ASSERT(index <= subject->length());
 
   if (!subject->IsFlat()) FlattenString(subject);
   AssertNoAllocation no_heap_allocation;  // ensure vectors stay valid
 
-  String* needle = String::cast(re->DataAt(JSRegExp::kAtomPatternIndex));
+  String* needle = String::cast(regexp->DataAt(JSRegExp::kAtomPatternIndex));
   int needle_len = needle->length();
   ASSERT(needle->IsFlat());
+  ASSERT_LT(0, needle_len);
 
-  if (needle_len != 0) {
-    if (index + needle_len > subject->length()) {
-      return isolate->factory()->null_value();
-    }
+  if (index + needle_len > subject->length()) {
+    return RegExpImpl::RE_FAILURE;
+  }
 
+  for (int i = 0; i < output_size; i += 2) {
     String::FlatContent needle_content = needle->GetFlatContent();
     String::FlatContent subject_content = subject->GetFlatContent();
     ASSERT(needle_content.IsFlat());
     ASSERT(subject_content.IsFlat());
     // dispatch on type of strings
     index = (needle_content.IsAscii()
              ? (subject_content.IsAscii()
                 ? SearchString(isolate,
                                subject_content.ToAsciiVector(),
                                needle_content.ToAsciiVector(),
                                index)
                 : SearchString(isolate,
                                subject_content.ToUC16Vector(),
                                needle_content.ToAsciiVector(),
                                index))
              : (subject_content.IsAscii()
                 ? SearchString(isolate,
                                subject_content.ToAsciiVector(),
                                needle_content.ToUC16Vector(),
                                index)
                 : SearchString(isolate,
                                subject_content.ToUC16Vector(),
                                needle_content.ToUC16Vector(),
                                index)));
-    if (index == -1) return isolate->factory()->null_value();
+    if (index == -1) {
+      return i / 2;  // Return number of matches.
+    } else {
+      output[i] = index;
+      output[i+1] = index + needle_len;
+      index += needle_len;
+    }
   }
-  ASSERT(last_match_info->HasFastObjectElements());
+  return output_size / 2;
+}
 
-  {
-    NoHandleAllocation no_handles;
-    FixedArray* array = FixedArray::cast(last_match_info->elements());
-    SetAtomLastCapture(array, *subject, index, index + needle_len);
-  }
+
+Handle<Object> RegExpImpl::AtomExec(Handle<JSRegExp> re,
+                                    Handle<String> subject,
+                                    int index,
+                                    Handle<JSArray> last_match_info) {
+  Isolate* isolate = re->GetIsolate();
+
+  static const int kNumRegisters = 2;
+  STATIC_ASSERT(kNumRegisters <= Isolate::kJSRegexpStaticOffsetsVectorSize);
+  int32_t* output_registers = isolate->jsregexp_static_offsets_vector();
+
+  int res = AtomExecRaw(re, subject, index, output_registers, kNumRegisters);
+
+  if (res == RegExpImpl::RE_FAILURE) return isolate->factory()->null_value();
+
+  ASSERT_EQ(res, RegExpImpl::RE_SUCCESS);
+  NoHandleAllocation no_handles;
+  FixedArray* array = FixedArray::cast(last_match_info->elements());
+  SetAtomLastCapture(array, *subject, output_registers[0], output_registers[1]);
   return last_match_info;
 }
 
 
 // Irregexp implementation.
 
 // Ensures that the regexp object contains a compiled version of the
 // source for either ASCII or non-ASCII strings.
 // If the compiled version doesn't already exist, it is compiled
 // from the source pattern.
@@ skipping 159 matching lines @@
 int RegExpImpl::IrregexpPrepare(Handle<JSRegExp> regexp,
                                 Handle<String> subject) {
   if (!subject->IsFlat()) FlattenString(subject);
 
   // Check the asciiness of the underlying storage.
   bool is_ascii = subject->IsAsciiRepresentationUnderneath();
   if (!EnsureCompiledIrregexp(regexp, subject, is_ascii)) return -1;
 
 #ifdef V8_INTERPRETED_REGEXP
   // Byte-code regexp needs space allocated for all its registers.
-  return IrregexpNumberOfRegisters(FixedArray::cast(regexp->data()));
+  // The result captures are copied to the start of the registers array
+  // if the match succeeds.  This way those registers are not clobbered
+  // when we set the last match info from last successful match.
+  return IrregexpNumberOfRegisters(FixedArray::cast(regexp->data())) +
+         (IrregexpNumberOfCaptures(FixedArray::cast(regexp->data())) + 1) * 2;
 #else  // V8_INTERPRETED_REGEXP
   // Native regexp only needs room to output captures. Registers are handled
   // internally.
   return (IrregexpNumberOfCaptures(FixedArray::cast(regexp->data())) + 1) * 2;
 #endif  // V8_INTERPRETED_REGEXP
 }
 
 
 int RegExpImpl::GlobalOffsetsVectorSize(Handle<JSRegExp> regexp,
                                         int registers_per_match,
                                         int* max_matches) {
 #ifdef V8_INTERPRETED_REGEXP
   // Global loop in interpreted regexp is not implemented.  Therefore we choose
   // the size of the offsets vector so that it can only store one match.
   *max_matches = 1;
   return registers_per_match;
 #else  // V8_INTERPRETED_REGEXP
-  int size = Max(registers_per_match, OffsetsVector::kStaticOffsetsVectorSize);
+  int size =
+      Max(registers_per_match, Isolate::kJSRegexpStaticOffsetsVectorSize);
   *max_matches = size / registers_per_match;
   return size;
 #endif  // V8_INTERPRETED_REGEXP
 }
 
 
-int RegExpImpl::IrregexpExecRaw(
-    Handle<JSRegExp> regexp,
-    Handle<String> subject,
-    int index,
-    Vector<int> output) {
+int RegExpImpl::IrregexpExecRaw(Handle<JSRegExp> regexp,
+                                Handle<String> subject,
+                                int index,
+                                int32_t* output,
+                                int output_size) {
   Isolate* isolate = regexp->GetIsolate();
 
   Handle<FixedArray> irregexp(FixedArray::cast(regexp->data()), isolate);
 
   ASSERT(index >= 0);
   ASSERT(index <= subject->length());
   ASSERT(subject->IsFlat());
 
   bool is_ascii = subject->IsAsciiRepresentationUnderneath();
 
 #ifndef V8_INTERPRETED_REGEXP
-  ASSERT(output.length() >= (IrregexpNumberOfCaptures(*irregexp) + 1) * 2);
+  ASSERT(output_size >= (IrregexpNumberOfCaptures(*irregexp) + 1) * 2);
   do {
     EnsureCompiledIrregexp(regexp, subject, is_ascii);
     Handle<Code> code(IrregexpNativeCode(*irregexp, is_ascii), isolate);
+    // The stack is used to allocate registers for the compiled regexp code.
+    // This means that in case of failure, the output registers array is left
+    // untouched and contains the capture results from the previous successful
+    // match.  We can use that to set the last match info lazily.
     NativeRegExpMacroAssembler::Result res =
         NativeRegExpMacroAssembler::Match(code,
                                           subject,
-                                          output.start(),
-                                          output.length(),
+                                          output,
+                                          output_size,
                                           index,
                                           isolate);
     if (res != NativeRegExpMacroAssembler::RETRY) {
       ASSERT(res != NativeRegExpMacroAssembler::EXCEPTION ||
              isolate->has_pending_exception());
       STATIC_ASSERT(
           static_cast<int>(NativeRegExpMacroAssembler::SUCCESS) == RE_SUCCESS);
       STATIC_ASSERT(
           static_cast<int>(NativeRegExpMacroAssembler::FAILURE) == RE_FAILURE);
       STATIC_ASSERT(static_cast<int>(NativeRegExpMacroAssembler::EXCEPTION)
                     == RE_EXCEPTION);
       return static_cast<IrregexpResult>(res);
     }
     // If result is RETRY, the string has changed representation, and we
     // must restart from scratch.
     // In this case, it means we must make sure we are prepared to handle
     // the, potentially, different subject (the string can switch between
     // being internal and external, and even between being ASCII and UC16,
     // but the characters are always the same).
     IrregexpPrepare(regexp, subject);
     is_ascii = subject->IsAsciiRepresentationUnderneath();
   } while (true);
   UNREACHABLE();
   return RE_EXCEPTION;
 #else  // V8_INTERPRETED_REGEXP
 
-  ASSERT(output.length() >= IrregexpNumberOfRegisters(*irregexp));
+  ASSERT(output_size >= IrregexpNumberOfRegisters(*irregexp));
   // We must have done EnsureCompiledIrregexp, so we can get the number of
   // registers.
-  int* register_vector = output.start();
   int number_of_capture_registers =
       (IrregexpNumberOfCaptures(*irregexp) + 1) * 2;
+  int32_t* raw_output = &output[number_of_capture_registers];
+  // We do not touch the actual capture result registers until we know there
+  // has been a match so that we can use those capture results to set the
+  // last match info.
   for (int i = number_of_capture_registers - 1; i >= 0; i--) {
-    register_vector[i] = -1;
+    raw_output[i] = -1;
   }
   Handle<ByteArray> byte_codes(IrregexpByteCode(*irregexp, is_ascii), isolate);
 
   IrregexpResult result = IrregexpInterpreter::Match(isolate,
                                                      byte_codes,
                                                      subject,
-                                                     register_vector,
+                                                     raw_output,
                                                      index);
+  if (result == RE_SUCCESS) {
+    // Copy capture results to the start of the registers array.
+    memcpy(output, raw_output, number_of_capture_registers * sizeof(int32_t));
+  }
   if (result == RE_EXCEPTION) {
     ASSERT(!isolate->has_pending_exception());
     isolate->StackOverflow();
   }
   return result;
 #endif  // V8_INTERPRETED_REGEXP
 }
 
 
-Handle<Object> RegExpImpl::IrregexpExec(Handle<JSRegExp> jsregexp,
+Handle<Object> RegExpImpl::IrregexpExec(Handle<JSRegExp> regexp,
                                         Handle<String> subject,
                                         int previous_index,
                                         Handle<JSArray> last_match_info) {
-  Isolate* isolate = jsregexp->GetIsolate();
-  ASSERT_EQ(jsregexp->TypeTag(), JSRegExp::IRREGEXP);
+  Isolate* isolate = regexp->GetIsolate();
+  ASSERT_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);
 
   // Prepare space for the return values.
-#ifdef V8_INTERPRETED_REGEXP
-#ifdef DEBUG
+#if defined(V8_INTERPRETED_REGEXP) && defined(DEBUG)
   if (FLAG_trace_regexp_bytecodes) {
-    String* pattern = jsregexp->Pattern();
+    String* pattern = regexp->Pattern();
     PrintF("\n\nRegexp match:   /%s/\n\n", *(pattern->ToCString()));
     PrintF("\n\nSubject string: '%s'\n\n", *(subject->ToCString()));
   }
 #endif
-#endif
-  int required_registers = RegExpImpl::IrregexpPrepare(jsregexp, subject);
+  int required_registers = RegExpImpl::IrregexpPrepare(regexp, subject);
   if (required_registers < 0) {
     // Compiling failed with an exception.
     ASSERT(isolate->has_pending_exception());
     return Handle<Object>::null();
   }
 
-  OffsetsVector registers(required_registers, isolate);
+  int32_t* output_registers;
+  if (required_registers > Isolate::kJSRegexpStaticOffsetsVectorSize) {
+    output_registers = NewArray<int32_t>(required_registers);
+  } else {
+    output_registers = isolate->jsregexp_static_offsets_vector();
+  }
 
-  int res = RegExpImpl::IrregexpExecRaw(jsregexp, subject, previous_index,
-                                        Vector<int>(registers.vector(),
-                                                    registers.length()));
+  int res = RegExpImpl::IrregexpExecRaw(
+      regexp, subject, previous_index, output_registers, required_registers);
   if (res == RE_SUCCESS) {
-    int capture_register_count =
-        (IrregexpNumberOfCaptures(FixedArray::cast(jsregexp->data())) + 1) * 2;
-    last_match_info->EnsureSize(capture_register_count + kLastMatchOverhead);
-    AssertNoAllocation no_gc;
-    int* register_vector = registers.vector();
-    FixedArray* array = FixedArray::cast(last_match_info->elements());
-    for (int i = 0; i < capture_register_count; i += 2) {
-      SetCapture(array, i, register_vector[i]);
-      SetCapture(array, i + 1, register_vector[i + 1]);
-    }
-    SetLastCaptureCount(array, capture_register_count);
-    SetLastSubject(array, *subject);
-    SetLastInput(array, *subject);
-    return last_match_info;
+    int capture_count =
+        IrregexpNumberOfCaptures(FixedArray::cast(regexp->data()));
+    return SetLastMatchInfo(
+        last_match_info, subject, capture_count, output_registers);
   }
   if (res == RE_EXCEPTION) {
     ASSERT(isolate->has_pending_exception());
     return Handle<Object>::null();
   }
   ASSERT(res == RE_FAILURE);
   return isolate->factory()->null_value();
 }
 
 
+Handle<JSArray> RegExpImpl::SetLastMatchInfo(Handle<JSArray> last_match_info,
+                                             Handle<String> subject,
+                                             int capture_count,
+                                             int32_t* match) {
+  int capture_register_count = (capture_count + 1) * 2;
+  last_match_info->EnsureSize(capture_register_count + kLastMatchOverhead);
+  AssertNoAllocation no_gc;
+  FixedArray* array = FixedArray::cast(last_match_info->elements());
+  if (match != NULL) {
+    for (int i = 0; i < capture_register_count; i += 2) {
+      SetCapture(array, i, match[i]);
+      SetCapture(array, i + 1, match[i + 1]);
+    }
+  }
+  SetLastCaptureCount(array, capture_register_count);
+  SetLastSubject(array, *subject);
+  SetLastInput(array, *subject);
+  return last_match_info;
+}
+
+
+int RegExpImpl::global_cache_num_matches_ = 0;
+int RegExpImpl::global_cache_max_matches_ = 0;
+int RegExpImpl::global_cache_current_match_index_ = 0;
+int RegExpImpl::global_cache_registers_per_match_ = 0;
+JSRegExp::Type RegExpImpl::global_cache_current_type_ = JSRegExp::ATOM;
+int32_t* RegExpImpl::global_cache_register_array_ = NULL;
+int RegExpImpl::global_cache_register_array_size_ = 0;
+
+
+int RegExpImpl::GlobalCacheInitialize(Handle<JSRegExp> regexp,
+                                      Handle<String> subject,
+                                      bool is_global,
+                                      Isolate* isolate) {
+  int num_registers = 0;
+#ifdef V8_INTERPRETED_REGEXP
+  bool interpreted = true;
+#else
+  bool interpreted = false;
+#endif  // V8_INTERPRETED_REGEXP
+
+  global_cache_current_type_ = regexp->TypeTag();
+  if (global_cache_current_type_ == JSRegExp::ATOM) {
+    static const int kAtomRegistersPerMatch = 2;
+    global_cache_registers_per_match_ = kAtomRegistersPerMatch;
+    // There is no distinction between interpreted and native for atom regexps.
+    interpreted = false;
+  } else {
+    global_cache_registers_per_match_ =
+        RegExpImpl::IrregexpPrepare(regexp, subject);
+    if (global_cache_registers_per_match_ < 0) return RE_EXCEPTION;
+  }
+
+  if (is_global && !interpreted) {
+    num_registers = Max(global_cache_registers_per_match_,
+                        Isolate::kJSRegexpStaticOffsetsVectorSize);
+    global_cache_max_matches_ =
+        num_registers / global_cache_registers_per_match_;
+  } else {
+    // Global loop in interpreted regexp is not implemented.  We choose
+    // the size of the offsets vector so that it can only store one match.
+    num_registers = global_cache_registers_per_match_;
+    global_cache_max_matches_ = 1;
+  }
+
+  if (global_cache_register_array_size_ >
+      Isolate::kJSRegexpStaticOffsetsVectorSize) {
+    DeleteArray(global_cache_register_array_);
+  }
+
+  if (num_registers > Isolate::kJSRegexpStaticOffsetsVectorSize) {
+    global_cache_register_array_ = NewArray<int32_t>(num_registers);
+  } else {
+    global_cache_register_array_ = isolate->jsregexp_static_offsets_vector();
+  }
+
+  global_cache_register_array_size_ = num_registers;
+
+  // Set state so that fetching the results the first time triggers a call
+  // to the compiled regexp.
+  global_cache_current_match_index_ = global_cache_max_matches_;
+  global_cache_num_matches_ = global_cache_max_matches_;
+  int32_t* last_match =
+      &global_cache_register_array_[global_cache_register_array_size_ -
+                                    global_cache_registers_per_match_];
+  last_match[0] = -1;
+  last_match[1] = 0;
+  return RE_SUCCESS;
+}
+
+
 // -------------------------------------------------------------------
 // Implementation of the Irregexp regular expression engine.
 //
 // The Irregexp regular expression engine is intended to be a complete
 // implementation of ECMAScript regular expressions.  It generates either
 // bytecodes or native code.
 
 //   The Irregexp regexp engine is structured in three steps.
 //   1) The parser generates an abstract syntax tree.  See ast.cc.
 //   2) From the AST a node network is created.  The nodes are all
@@ skipping 5324 matching lines @@
   }
 
   return compiler.Assemble(&macro_assembler,
                            node,
                            data->capture_count,
                            pattern);
 }
 
 
 }}  // namespace v8::internal