Reland regexp global optimizations.

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 2556 matching lines @@
   FixedArrayBuilder array_builder_;
   Handle<String> subject_;
   int character_count_;
   bool is_ascii_;
 };
 
 
 class CompiledReplacement {
  public:
   explicit CompiledReplacement(Zone* zone)
-      : parts_(1, zone), replacement_substrings_(0, zone),
-        simple_hint_(false),
-        zone_(zone) {}
+      : parts_(1, zone), replacement_substrings_(0, zone), zone_(zone) {}
 
-  void Compile(Handle<String> replacement,
+  // Return whether the replacement is simple.
+  bool Compile(Handle<String> replacement,
                int capture_count,
                int subject_length);
 
+  // Use Apply only if Compile returned false.
   void Apply(ReplacementStringBuilder* builder,
              int match_from,
              int match_to,
-             Handle<JSArray> last_match_info);
+             int32_t* match);
 
   // Number of distinct parts of the replacement pattern.
   int parts() {
     return parts_.length();
   }
 
-  bool simple_hint() {
-    return simple_hint_;
-  }
-
   Zone* zone() const { return zone_; }
 
  private:
   enum PartType {
     SUBJECT_PREFIX = 1,
     SUBJECT_SUFFIX,
     SUBJECT_CAPTURE,
     REPLACEMENT_SUBSTRING,
     REPLACEMENT_STRING,
 
@@ skipping 40 matching lines @@
     // tag == REPLACEMENT_STRING:    data is index into array of substrings
     //                               of the replacement string.
     // tag <= 0: Temporary representation of the substring of the replacement
     //           string ranging over -tag .. data.
     //           Is replaced by REPLACEMENT_{SUB,}STRING when we create the
     //           substring objects.
     int data;
   };
 
   template<typename Char>
-  static bool ParseReplacementPattern(ZoneList<ReplacementPart>* parts,
-                                      Vector<Char> characters,
-                                      int capture_count,
-                                      int subject_length,
-                                      Zone* zone) {
+  bool ParseReplacementPattern(ZoneList<ReplacementPart>* parts,
+                               Vector<Char> characters,
+                               int capture_count,
+                               int subject_length,
+                               Zone* zone) {
     int length = characters.length();
     int last = 0;
     for (int i = 0; i < length; i++) {
       Char c = characters[i];
       if (c == '$') {
         int next_index = i + 1;
         if (next_index == length) {  // No next character!
           break;
         }
         Char c2 = characters[next_index];
@@ skipping 73 matching lines @@
           break;
         }
         default:
           i = next_index;
           break;
         }
       }
     }
     if (length > last) {
       if (last == 0) {
-        parts->Add(ReplacementPart::ReplacementString(), zone);
+        // Replacement is simple.  Do not use Apply to do the replacement.
         return true;
       } else {
         parts->Add(ReplacementPart::ReplacementSubString(last, length), zone);
       }
     }
     return false;
   }
 
   ZoneList<ReplacementPart> parts_;
   ZoneList<Handle<String> > replacement_substrings_;
-  bool simple_hint_;
   Zone* zone_;
 };
 
 
-void CompiledReplacement::Compile(Handle<String> replacement,
+bool CompiledReplacement::Compile(Handle<String> replacement,
                                   int capture_count,
                                   int subject_length) {
   {
     AssertNoAllocation no_alloc;
     String::FlatContent content = replacement->GetFlatContent();
     ASSERT(content.IsFlat());
+    bool simple = false;
     if (content.IsAscii()) {
-      simple_hint_ = ParseReplacementPattern(&parts_,
-                                             content.ToAsciiVector(),
-                                             capture_count,
-                                             subject_length,
-                                             zone());
+      simple = ParseReplacementPattern(&parts_,
+                                       content.ToAsciiVector(),
+                                       capture_count,
+                                       subject_length,
+                                       zone());
     } else {
       ASSERT(content.IsTwoByte());
-      simple_hint_ = ParseReplacementPattern(&parts_,
-                                             content.ToUC16Vector(),
-                                             capture_count,
-                                             subject_length,
-                                             zone());
+      simple = ParseReplacementPattern(&parts_,
+                                       content.ToUC16Vector(),
+                                       capture_count,
+                                       subject_length,
+                                       zone());
     }
+    if (simple) return true;
   }
+
   Isolate* isolate = replacement->GetIsolate();
   // Find substrings of replacement string and create them as String objects.
   int substring_index = 0;
   for (int i = 0, n = parts_.length(); i < n; i++) {
     int tag = parts_[i].tag;
     if (tag <= 0) {  // A replacement string slice.
       int from = -tag;
       int to = parts_[i].data;
       replacement_substrings_.Add(
           isolate->factory()->NewSubString(replacement, from, to), zone());
       parts_[i].tag = REPLACEMENT_SUBSTRING;
       parts_[i].data = substring_index;
       substring_index++;
     } else if (tag == REPLACEMENT_STRING) {
       replacement_substrings_.Add(replacement, zone());
       parts_[i].data = substring_index;
       substring_index++;
     }
   }
+  return false;
 }
 
 
 void CompiledReplacement::Apply(ReplacementStringBuilder* builder,
                                 int match_from,
                                 int match_to,
-                                Handle<JSArray> last_match_info) {
+                                int32_t* match) {
+  ASSERT_LT(0, parts_.length());
   for (int i = 0, n = parts_.length(); i < n; i++) {
     ReplacementPart part = parts_[i];
     switch (part.tag) {
       case SUBJECT_PREFIX:
         if (match_from > 0) builder->AddSubjectSlice(0, match_from);
         break;
       case SUBJECT_SUFFIX: {
         int subject_length = part.data;
         if (match_to < subject_length) {
           builder->AddSubjectSlice(match_to, subject_length);
         }
         break;
       }
       case SUBJECT_CAPTURE: {
         int capture = part.data;
-        FixedArray* match_info = FixedArray::cast(last_match_info->elements());
-        int from = RegExpImpl::GetCapture(match_info, capture * 2);
-        int to = RegExpImpl::GetCapture(match_info, capture * 2 + 1);
+        int from = match[capture * 2];
+        int to = match[capture * 2 + 1];
         if (from >= 0 && to > from) {
           builder->AddSubjectSlice(from, to);
         }
         break;
       }
       case REPLACEMENT_SUBSTRING:
       case REPLACEMENT_STRING:
         builder->AddString(replacement_substrings_[part.data]);
         break;
       default:
@@ skipping 101 matching lines @@
                           pattern_content.ToUC16Vector(),
                           indices,
                           limit,
                           zone);
       }
     }
   }
 }
 
 
-// Two smis before and after the match, for very long strings.
-const int kMaxBuilderEntriesPerRegExpMatch = 5;
-
-
-static void SetLastMatchInfoNoCaptures(Handle<String> subject,
-                                       Handle<JSArray> last_match_info,
-                                       int match_start,
-                                       int match_end) {
-  // Fill last_match_info with a single capture.
-  last_match_info->EnsureSize(2 + RegExpImpl::kLastMatchOverhead);
-  AssertNoAllocation no_gc;
-  FixedArray* elements = FixedArray::cast(last_match_info->elements());
-  RegExpImpl::SetLastCaptureCount(elements, 2);
-  RegExpImpl::SetLastInput(elements, *subject);
-  RegExpImpl::SetLastSubject(elements, *subject);
-  RegExpImpl::SetCapture(elements, 0, match_start);
-  RegExpImpl::SetCapture(elements, 1, match_end);
-}
-
-
-template <typename SubjectChar, typename PatternChar>
-static bool SearchStringMultiple(Isolate* isolate,
-                                 Vector<const SubjectChar> subject,
-                                 Vector<const PatternChar> pattern,
-                                 String* pattern_string,
-                                 FixedArrayBuilder* builder,
-                                 int* match_pos) {
-  int pos = *match_pos;
-  int subject_length = subject.length();
-  int pattern_length = pattern.length();
-  int max_search_start = subject_length - pattern_length;
-  StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
-  while (pos <= max_search_start) {
-    if (!builder->HasCapacity(kMaxBuilderEntriesPerRegExpMatch)) {
-      *match_pos = pos;
-      return false;
-    }
-    // Position of end of previous match.
-    int match_end = pos + pattern_length;
-    int new_pos = search.Search(subject, match_end);
-    if (new_pos >= 0) {
-      // A match.
-      if (new_pos > match_end) {
-        ReplacementStringBuilder::AddSubjectSlice(builder,
-            match_end,
-            new_pos);
-      }
-      pos = new_pos;
-      builder->Add(pattern_string);
-    } else {
-      break;
-    }
-  }
-
-  if (pos < max_search_start) {
-    ReplacementStringBuilder::AddSubjectSlice(builder,
-                                              pos + pattern_length,
-                                              subject_length);
-  }
-  *match_pos = pos;
-  return true;
-}
-
-
-
-
 template<typename ResultSeqString>
 MUST_USE_RESULT static MaybeObject* StringReplaceAtomRegExpWithString(
     Isolate* isolate,
     Handle<String> subject,
     Handle<JSRegExp> pattern_regexp,
     Handle<String> replacement,
-    Handle<JSArray> last_match_info,
-    Zone* zone) {
+    Handle<JSArray> last_match_info) {
   ASSERT(subject->IsFlat());
   ASSERT(replacement->IsFlat());
 
-  ZoneScope zone_space(isolate->runtime_zone(), DELETE_ON_EXIT);
-  ZoneList<int> indices(8, isolate->runtime_zone());
+  Zone* zone = isolate->runtime_zone();
+  ZoneScope zone_space(zone, DELETE_ON_EXIT);
+  ZoneList<int> indices(8, zone);
   ASSERT_EQ(JSRegExp::ATOM, pattern_regexp->TypeTag());
   String* pattern =
       String::cast(pattern_regexp->DataAt(JSRegExp::kAtomPatternIndex));
   int subject_len = subject->length();
   int pattern_len = pattern->length();
   int replacement_len = replacement->length();
 
-  FindStringIndicesDispatch(isolate, *subject, pattern, &indices, 0xffffffff,
-                            zone);
+  FindStringIndicesDispatch(
+      isolate, *subject, pattern, &indices, 0xffffffff, zone);
 
   int matches = indices.length();
   if (matches == 0) return *subject;
 
   // Detect integer overflow.
   int64_t result_len_64 =
       (static_cast<int64_t>(replacement_len) -
        static_cast<int64_t>(pattern_len)) *
       static_cast<int64_t>(matches) +
       static_cast<int64_t>(subject_len);
@@ skipping 34 matching lines @@
     subject_pos = indices.at(i) + pattern_len;
   }
   // Add remaining subject content at the end.
   if (subject_pos < subject_len) {
     String::WriteToFlat(*subject,
                         result->GetChars() + result_pos,
                         subject_pos,
                         subject_len);
   }
 
-  SetLastMatchInfoNoCaptures(subject,
-                             last_match_info,
-                             indices.at(matches - 1),
-                             indices.at(matches - 1) + pattern_len);
+  int32_t match_indices[] = { indices.at(matches - 1),
+                              indices.at(matches - 1) + pattern_len };
+  RegExpImpl::SetLastMatchInfo(last_match_info, subject, 0, match_indices);
 
   return *result;
 }
 
 
 MUST_USE_RESULT static MaybeObject* StringReplaceRegExpWithString(
     Isolate* isolate,
-    String* subject,
-    JSRegExp* regexp,
-    String* replacement,
-    JSArray* last_match_info,
-    Zone* zone) {
+    Handle<String> subject,
+    Handle<JSRegExp> regexp,
+    Handle<String> replacement,
+    Handle<JSArray> last_match_info) {
   ASSERT(subject->IsFlat());
   ASSERT(replacement->IsFlat());
 
-  HandleScope handles(isolate);
-
-  int length = subject->length();
-  Handle<String> subject_handle(subject);
-  Handle<JSRegExp> regexp_handle(regexp);
-  Handle<String> replacement_handle(replacement);
-  Handle<JSArray> last_match_info_handle(last_match_info);
-  Handle<Object> match = RegExpImpl::Exec(regexp_handle,
-                                          subject_handle,
-                                          0,
-                                          last_match_info_handle);
-  if (match.is_null()) {
-    return Failure::Exception();
-  }
-  if (match->IsNull()) {
-    return *subject_handle;
-  }
-
-  int capture_count = regexp_handle->CaptureCount();
+  bool is_global = regexp->GetFlags().is_global();
+  int capture_count = regexp->CaptureCount();
+  int subject_length = subject->length();
 
   // CompiledReplacement uses zone allocation.
+  Zone* zone = isolate->runtime_zone();
   ZoneScope zonescope(zone, DELETE_ON_EXIT);
   CompiledReplacement compiled_replacement(zone);
-
-  compiled_replacement.Compile(replacement_handle,
-                               capture_count,
-                               length);
-
-  bool is_global = regexp_handle->GetFlags().is_global();
+  bool simple_replace = compiled_replacement.Compile(replacement,
+                                                     capture_count,
+                                                     subject_length);
 
   // Shortcut for simple non-regexp global replacements
   if (is_global &&
-          regexp_handle->TypeTag() == JSRegExp::ATOM &&
-           compiled_replacement.simple_hint()) {
-         if (subject_handle->HasOnlyAsciiChars() &&
-             replacement_handle->HasOnlyAsciiChars()) {
+      regexp->TypeTag() == JSRegExp::ATOM &&
+      simple_replace) {
+    if (subject->HasOnlyAsciiChars() && replacement->HasOnlyAsciiChars()) {
       return StringReplaceAtomRegExpWithString<SeqAsciiString>(
-                 isolate,
-                 subject_handle,
-                 regexp_handle,
-                 replacement_handle,
-                 last_match_info_handle,
-                 zone);
-         } else {
+          isolate, subject, regexp, replacement, last_match_info);
+    } else {
       return StringReplaceAtomRegExpWithString<SeqTwoByteString>(
-                 isolate,
-                 subject_handle,
-                 regexp_handle,
-                 replacement_handle,
-                 last_match_info_handle,
-                 zone);
+          isolate, subject, regexp, replacement, last_match_info);
     }
   }
 
+  RegExpImpl::GlobalCache global_cache(regexp, subject, is_global, isolate);
+  if (global_cache.HasException()) return Failure::Exception();
+
+  int32_t* current_match = global_cache.FetchNext();
+  if (current_match == NULL) {
+    if (global_cache.HasException()) return Failure::Exception();
+    return *subject;
+  }
+
   // Guessing the number of parts that the final result string is built
   // from. Global regexps can match any number of times, so we guess
   // conservatively.
   int expected_parts =
       (compiled_replacement.parts() + 1) * (is_global ? 4 : 1) + 1;
   ReplacementStringBuilder builder(isolate->heap(),
-                                   subject_handle,
+                                   subject,
                                    expected_parts);
 
-  // Index of end of last match.
-  int prev = 0;
-
-
   // Number of parts added by compiled replacement plus preceeding
   // string and possibly suffix after last match.  It is possible for
   // all components to use two elements when encoded as two smis.
   const int parts_added_per_loop = 2 * (compiled_replacement.parts() + 2);
-  bool matched = true;
+
+  int prev = 0;
+
   do {
-    ASSERT(last_match_info_handle->HasFastObjectElements());
-    // Increase the capacity of the builder before entering local handle-scope,
-    // so its internal buffer can safely allocate a new handle if it grows.
     builder.EnsureCapacity(parts_added_per_loop);
 
-    HandleScope loop_scope(isolate);
-    int start, end;
-    {
-      AssertNoAllocation match_info_array_is_not_in_a_handle;
-      FixedArray* match_info_array =
-          FixedArray::cast(last_match_info_handle->elements());
-
-      ASSERT_EQ(capture_count * 2 + 2,
-                RegExpImpl::GetLastCaptureCount(match_info_array));
-      start = RegExpImpl::GetCapture(match_info_array, 0);
-      end = RegExpImpl::GetCapture(match_info_array, 1);
-    }
+    int start = current_match[0];
+    int end = current_match[1];
 
     if (prev < start) {
       builder.AddSubjectSlice(prev, start);
     }
-    compiled_replacement.Apply(&builder,
-                               start,
-                               end,
-                               last_match_info_handle);
 
+    if (simple_replace) {
+      builder.AddString(replacement);
+    } else {
+      compiled_replacement.Apply(&builder,
+                                 start,
+                                 end,
+                                 current_match);
+    }
     prev = end;
 
     // Only continue checking for global regexps.
     if (!is_global) break;
 
-    // Continue from where the match ended, unless it was an empty match.
-    int next = end;
-    if (start == end) {
-      next = end + 1;
-      if (next > length) break;
-    }
+    current_match = global_cache.FetchNext();
+  } while (current_match != NULL);
 
-    match = RegExpImpl::Exec(regexp_handle,
-                             subject_handle,
-                             next,
-                             last_match_info_handle);
-    if (match.is_null()) {
-      return Failure::Exception();
-    }
-    matched = !match->IsNull();
-  } while (matched);
+  if (global_cache.HasException()) return Failure::Exception();
 
-  if (prev < length) {
-    builder.AddSubjectSlice(prev, length);
+  if (prev < subject_length) {
+    builder.EnsureCapacity(2);
+    builder.AddSubjectSlice(prev, subject_length);
   }
 
+  RegExpImpl::SetLastMatchInfo(last_match_info,
+                               subject,
+                               capture_count,
+                               global_cache.LastSuccessfulMatch());
+
   return *(builder.ToString());
 }
 
 
 template <typename ResultSeqString>
 MUST_USE_RESULT static MaybeObject* StringReplaceRegExpWithEmptyString(
     Isolate* isolate,
-    String* subject,
-    JSRegExp* regexp,
-    JSArray* last_match_info,
-    Zone* zone) {
+    Handle<String> subject,
+    Handle<JSRegExp> regexp,
+    Handle<JSArray> last_match_info) {
   ASSERT(subject->IsFlat());
 
-  HandleScope handles(isolate);
-
-  Handle<String> subject_handle(subject);
-  Handle<JSRegExp> regexp_handle(regexp);
-  Handle<JSArray> last_match_info_handle(last_match_info);
+  bool is_global = regexp->GetFlags().is_global();
 
   // Shortcut for simple non-regexp global replacements
-  if (regexp_handle->GetFlags().is_global() &&
-      regexp_handle->TypeTag() == JSRegExp::ATOM) {
-    Handle<String> empty_string_handle(HEAP->empty_string());
-    if (subject_handle->HasOnlyAsciiChars()) {
+  if (is_global &&
+      regexp->TypeTag() == JSRegExp::ATOM) {
+    Handle<String> empty_string(HEAP->empty_string());
+    if (subject->HasOnlyAsciiChars()) {
       return StringReplaceAtomRegExpWithString<SeqAsciiString>(
           isolate,
-          subject_handle,
-          regexp_handle,
-          empty_string_handle,
-          last_match_info_handle,
-          zone);
+          subject,
+          regexp,
+          empty_string,
+          last_match_info);
     } else {
       return StringReplaceAtomRegExpWithString<SeqTwoByteString>(
           isolate,
-          subject_handle,
-          regexp_handle,
-          empty_string_handle,
-          last_match_info_handle,
-          zone);
+          subject,
+          regexp,
+          empty_string,
+          last_match_info);
     }
   }
 
-  Handle<Object> match = RegExpImpl::Exec(regexp_handle,
-                                          subject_handle,
-                                          0,
-                                          last_match_info_handle);
-  if (match.is_null()) return Failure::Exception();
-  if (match->IsNull()) return *subject_handle;
+  RegExpImpl::GlobalCache global_cache(regexp, subject, is_global, isolate);
+  if (global_cache.HasException()) return Failure::Exception();
 
-  ASSERT(last_match_info_handle->HasFastObjectElements());
-
-  int start, end;
-  {
-    AssertNoAllocation match_info_array_is_not_in_a_handle;
-    FixedArray* match_info_array =
-        FixedArray::cast(last_match_info_handle->elements());
-
-    start = RegExpImpl::GetCapture(match_info_array, 0);
-    end = RegExpImpl::GetCapture(match_info_array, 1);
+  int32_t* current_match = global_cache.FetchNext();
+  if (current_match == NULL) {
+    if (global_cache.HasException()) return Failure::Exception();
+    return *subject;
   }
 
-  bool global = regexp_handle->GetFlags().is_global();
+  int start = current_match[0];
+  int end = current_match[1];
+  int capture_count = regexp->CaptureCount();
+  int subject_length = subject->length();
 
-  if (start == end && !global) return *subject_handle;
+  int new_length = subject_length - (end - start);
+  if (new_length == 0) return isolate->heap()->empty_string();
 
-  int length = subject_handle->length();
-  int new_length = length - (end - start);
-  if (new_length == 0) {
-    return isolate->heap()->empty_string();
-  }
   Handle<ResultSeqString> answer;
   if (ResultSeqString::kHasAsciiEncoding) {
     answer = Handle<ResultSeqString>::cast(
         isolate->factory()->NewRawAsciiString(new_length));
   } else {
     answer = Handle<ResultSeqString>::cast(
         isolate->factory()->NewRawTwoByteString(new_length));
   }
 
-  // If the regexp isn't global, only match once.
-  if (!global) {
-    if (start > 0) {
-      String::WriteToFlat(*subject_handle,
-                          answer->GetChars(),
-                          0,
-                          start);
+  if (!is_global) {
+    RegExpImpl::SetLastMatchInfo(
+        last_match_info, subject, capture_count, current_match);
+    if (start == end) {
+      return *subject;
+    } else {
+      if (start > 0) {
+        String::WriteToFlat(*subject, answer->GetChars(), 0, start);
+      }
+      if (end < subject_length) {
+        String::WriteToFlat(
+            *subject, answer->GetChars() + start, end, subject_length);
+      }
+      return *answer;
     }
-    if (end < length) {
-      String::WriteToFlat(*subject_handle,
-                          answer->GetChars() + start,
-                          end,
-                          length);
-    }
-    return *answer;
   }
 
-  int prev = 0;  // Index of end of last match.
-  int next = 0;  // Start of next search (prev unless last match was empty).
+  int prev = 0;
   int position = 0;
 
   do {
+    start = current_match[0];
+    end = current_match[1];
     if (prev < start) {
       // Add substring subject[prev;start] to answer string.
-      String::WriteToFlat(*subject_handle,
-                          answer->GetChars() + position,
-                          prev,
-                          start);
+      String::WriteToFlat(
+          *subject, answer->GetChars() + position, prev, start);
       position += start - prev;
     }
     prev = end;
-    next = end;
-    // Continue from where the match ended, unless it was an empty match.
-    if (start == end) {
-      next++;
-      if (next > length) break;
-    }
-    match = RegExpImpl::Exec(regexp_handle,
-                             subject_handle,
-                             next,
-                             last_match_info_handle);
-    if (match.is_null()) return Failure::Exception();
-    if (match->IsNull()) break;
 
-    ASSERT(last_match_info_handle->HasFastObjectElements());
-    HandleScope loop_scope(isolate);
-    {
-      AssertNoAllocation match_info_array_is_not_in_a_handle;
-      FixedArray* match_info_array =
-          FixedArray::cast(last_match_info_handle->elements());
-      start = RegExpImpl::GetCapture(match_info_array, 0);
-      end = RegExpImpl::GetCapture(match_info_array, 1);
-    }
-  } while (true);
+    current_match = global_cache.FetchNext();
+  } while (current_match != NULL);
 
-  if (prev < length) {
+  if (global_cache.HasException()) return Failure::Exception();
+
+  RegExpImpl::SetLastMatchInfo(last_match_info,
+                               subject,
+                               capture_count,
+                               global_cache.LastSuccessfulMatch());
+
+  if (prev < subject_length) {
     // Add substring subject[prev;length] to answer string.
-    String::WriteToFlat(*subject_handle,
-                        answer->GetChars() + position,
-                        prev,
-                        length);
-    position += length - prev;
+    String::WriteToFlat(
+        *subject, answer->GetChars() + position, prev, subject_length);
+    position += subject_length - prev;
   }
 
-  if (position == 0) {
-    return isolate->heap()->empty_string();
-  }
+  if (position == 0) return isolate->heap()->empty_string();
 
   // Shorten string and fill
   int string_size = ResultSeqString::SizeFor(position);
   int allocated_string_size = ResultSeqString::SizeFor(new_length);
   int delta = allocated_string_size - string_size;
 
   answer->set_length(position);
   if (delta == 0) return *answer;
 
   Address end_of_string = answer->address() + string_size;
   isolate->heap()->CreateFillerObjectAt(end_of_string, delta);
   if (Marking::IsBlack(Marking::MarkBitFrom(*answer))) {
     MemoryChunk::IncrementLiveBytesFromMutator(answer->address(), -delta);
   }
 
   return *answer;
 }
 
 
 RUNTIME_FUNCTION(MaybeObject*, Runtime_StringReplaceRegExpWithString) {
   ASSERT(args.length() == 4);
 
-  CONVERT_ARG_CHECKED(String, subject, 0);
-  if (!subject->IsFlat()) {
-    Object* flat_subject;
-    { MaybeObject* maybe_flat_subject = subject->TryFlatten();
-      if (!maybe_flat_subject->ToObject(&flat_subject)) {
-        return maybe_flat_subject;
-      }
-    }
-    subject = String::cast(flat_subject);
-  }
+  HandleScope scope(isolate);
 
-  CONVERT_ARG_CHECKED(String, replacement, 2);
-  if (!replacement->IsFlat()) {
-    Object* flat_replacement;
-    { MaybeObject* maybe_flat_replacement = replacement->TryFlatten();
-      if (!maybe_flat_replacement->ToObject(&flat_replacement)) {
-        return maybe_flat_replacement;
-      }
-    }
-    replacement = String::cast(flat_replacement);
-  }
+  CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
+  CONVERT_ARG_HANDLE_CHECKED(String, replacement, 2);
+  CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1);
+  CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 3);
 
-  CONVERT_ARG_CHECKED(JSRegExp, regexp, 1);
-  CONVERT_ARG_CHECKED(JSArray, last_match_info, 3);
+  if (!subject->IsFlat()) subject = FlattenGetString(subject);
+
+  if (!replacement->IsFlat()) replacement = FlattenGetString(replacement);
 
   ASSERT(last_match_info->HasFastObjectElements());
 
-  Zone* zone = isolate->runtime_zone();
   if (replacement->length() == 0) {
     if (subject->HasOnlyAsciiChars()) {
       return StringReplaceRegExpWithEmptyString<SeqAsciiString>(
-          isolate, subject, regexp, last_match_info, zone);
+          isolate, subject, regexp, last_match_info);
     } else {
       return StringReplaceRegExpWithEmptyString<SeqTwoByteString>(
-          isolate, subject, regexp, last_match_info, zone);
+          isolate, subject, regexp, last_match_info);
     }
   }
 
-  return StringReplaceRegExpWithString(isolate,
-                                       subject,
-                                       regexp,
-                                       replacement,
-                                       last_match_info,
-                                       zone);
+  return StringReplaceRegExpWithString(
+      isolate, subject, regexp, replacement, last_match_info);
 }
 
 
 Handle<String> Runtime::StringReplaceOneCharWithString(Isolate* isolate,
                                                        Handle<String> subject,
                                                        Handle<String> search,
                                                        Handle<String> replace,
                                                        bool* found,
                                                        int recursion_limit) {
   if (recursion_limit == 0) return Handle<String>::null();
@@ skipping 302 matching lines @@
 
 
 RUNTIME_FUNCTION(MaybeObject*, Runtime_StringMatch) {
   ASSERT_EQ(3, args.length());
 
   CONVERT_ARG_HANDLE_CHECKED(String, subject, 0);
   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 1);
   CONVERT_ARG_HANDLE_CHECKED(JSArray, regexp_info, 2);
   HandleScope handles;
 
-  Handle<Object> match = RegExpImpl::Exec(regexp, subject, 0, regexp_info);
+  RegExpImpl::GlobalCache global_cache(regexp, subject, true, isolate);
+  if (global_cache.HasException()) return Failure::Exception();
 
-  if (match.is_null()) {
-    return Failure::Exception();
-  }
-  if (match->IsNull()) {
-    return isolate->heap()->null_value();
-  }
-  int length = subject->length();
+  int capture_count = regexp->CaptureCount();
 
   Zone* zone = isolate->runtime_zone();
   ZoneScope zone_space(zone, DELETE_ON_EXIT);
   ZoneList<int> offsets(8, zone);
-  int start;
-  int end;
-  do {
-    {
-      AssertNoAllocation no_alloc;
-      FixedArray* elements = FixedArray::cast(regexp_info->elements());
-      start = Smi::cast(elements->get(RegExpImpl::kFirstCapture))->value();
-      end = Smi::cast(elements->get(RegExpImpl::kFirstCapture + 1))->value();
-    }
-    offsets.Add(start, zone);
-    offsets.Add(end, zone);
-    if (start == end) if (++end > length) break;
-    match = RegExpImpl::Exec(regexp, subject, end, regexp_info);
-    if (match.is_null()) {
-      return Failure::Exception();
-    }
-  } while (!match->IsNull());
+
+  while (true) {
+    int32_t* match = global_cache.FetchNext();
+    if (match == NULL) break;
+    offsets.Add(match[0], zone);  // start
+    offsets.Add(match[1], zone);  // end
+  }
+
+  if (global_cache.HasException()) return Failure::Exception();
+
+  if (offsets.length() == 0) {
+    // Not a single match.
+    return isolate->heap()->null_value();
+  }
+
+  RegExpImpl::SetLastMatchInfo(regexp_info,
+                               subject,
+                               capture_count,
+                               global_cache.LastSuccessfulMatch());
+
   int matches = offsets.length() / 2;
   Handle<FixedArray> elements = isolate->factory()->NewFixedArray(matches);
-  Handle<String> substring = isolate->factory()->
-    NewSubString(subject, offsets.at(0), offsets.at(1));
+  Handle<String> substring =
+      isolate->factory()->NewSubString(subject, offsets.at(0), offsets.at(1));
   elements->set(0, *substring);
-  for (int i = 1; i < matches ; i++) {
+  for (int i = 1; i < matches; i++) {
+    HandleScope temp_scope(isolate);
     int from = offsets.at(i * 2);
     int to = offsets.at(i * 2 + 1);
-    Handle<String> substring = isolate->factory()->
-        NewProperSubString(subject, from, to);
+    Handle<String> substring =
+        isolate->factory()->NewProperSubString(subject, from, to);
     elements->set(i, *substring);
   }
   Handle<JSArray> result = isolate->factory()->NewJSArrayWithElements(elements);
   result->set_length(Smi::FromInt(matches));
   return *result;
 }
 
 
-static bool SearchStringMultiple(Isolate* isolate,
-                                 Handle<String> subject,
-                                 Handle<String> pattern,
-                                 Handle<JSArray> last_match_info,
-                                 FixedArrayBuilder* builder) {
-  ASSERT(subject->IsFlat());
-  ASSERT(pattern->IsFlat());
-
-  // Treating as if a previous match was before first character.
-  int match_pos = -pattern->length();
-
-  for (;;) {  // Break when search complete.
-    builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
-    AssertNoAllocation no_gc;
-    String::FlatContent subject_content = subject->GetFlatContent();
-    String::FlatContent pattern_content = pattern->GetFlatContent();
-    if (subject_content.IsAscii()) {
-      Vector<const char> subject_vector = subject_content.ToAsciiVector();
-      if (pattern_content.IsAscii()) {
-        if (SearchStringMultiple(isolate,
-                                 subject_vector,
-                                 pattern_content.ToAsciiVector(),
-                                 *pattern,
-                                 builder,
-                                 &match_pos)) break;
-      } else {
-        if (SearchStringMultiple(isolate,
-                                 subject_vector,
-                                 pattern_content.ToUC16Vector(),
-                                 *pattern,
-                                 builder,
-                                 &match_pos)) break;
-      }
-    } else {
-      Vector<const uc16> subject_vector = subject_content.ToUC16Vector();
-      if (pattern_content.IsAscii()) {
-        if (SearchStringMultiple(isolate,
-                                 subject_vector,
-                                 pattern_content.ToAsciiVector(),
-                                 *pattern,
-                                 builder,
-                                 &match_pos)) break;
-      } else {
-        if (SearchStringMultiple(isolate,
-                                 subject_vector,
-                                 pattern_content.ToUC16Vector(),
-                                 *pattern,
-                                 builder,
-                                 &match_pos)) break;
-      }
-    }
-  }
-
-  if (match_pos >= 0) {
-    SetLastMatchInfoNoCaptures(subject,
-                               last_match_info,
-                               match_pos,
-                               match_pos + pattern->length());
-    return true;
-  }
-  return false;  // No matches at all.
-}
-
-
-static int SearchRegExpNoCaptureMultiple(
+// 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>
+static int SearchRegExpMultiple(
     Isolate* isolate,
     Handle<String> subject,
     Handle<JSRegExp> regexp,
     Handle<JSArray> last_match_array,
     FixedArrayBuilder* builder) {
   ASSERT(subject->IsFlat());
-  ASSERT(regexp->CaptureCount() == 0);
+  ASSERT_NE(has_capture, regexp->CaptureCount() == 0);
+
+  RegExpImpl::GlobalCache global_cache(regexp, subject, true, isolate);
+  if (global_cache.HasException()) return RegExpImpl::RE_EXCEPTION;
+
+  int capture_count = regexp->CaptureCount();
+  int subject_length = subject->length();
+
+  // Position to search from.
   int match_start = -1;
   int match_end = 0;
-  int pos = 0;
-  int registers_per_match = RegExpImpl::IrregexpPrepare(regexp, subject);
-  if (registers_per_match < 0) return RegExpImpl::RE_EXCEPTION;
+  bool first = true;
 
-  int max_matches;
-  int num_registers = RegExpImpl::GlobalOffsetsVectorSize(regexp,
-                                                          registers_per_match,
-                                                          &max_matches);
-  OffsetsVector registers(num_registers, isolate);
-  Vector<int32_t> register_vector(registers.vector(), registers.length());
-  int subject_length = subject->length();
-  bool first = true;
-  for (;;) {  // Break on failure, return on exception.
-    int num_matches = RegExpImpl::IrregexpExecRaw(regexp,
-                                                  subject,
-                                                  pos,
-                                                  register_vector);
-    if (num_matches > 0) {
-      for (int match_index = 0; match_index < num_matches; match_index++) {
-        int32_t* current_match = &register_vector[match_index * 2];
-        match_start = current_match[0];
-        builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
-        if (match_end < match_start) {
-          ReplacementStringBuilder::AddSubjectSlice(builder,
-                                                    match_end,
-                                                    match_start);
-        }
-        match_end = current_match[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;
-        }
+  // Two smis before and after the match, for very long strings.
+  static const int kMaxBuilderEntriesPerRegExpMatch = 5;
+
+  while (true) {
+    int32_t* current_match = global_cache.FetchNext();
+    if (current_match == NULL) break;
+    match_start = current_match[0];
+    builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
+    if (match_end < match_start) {
+      ReplacementStringBuilder::AddSubjectSlice(builder,
+                                                match_end,
+                                                match_start);
+    }
+    match_end = current_match[1];
+    {
+      // Avoid accumulating new handles inside loop.
+      HandleScope temp_scope(isolate);
+      Handle<String> match;
+      if (!first) {
+        match = isolate->factory()->NewProperSubString(subject,
+                                                       match_start,
+                                                       match_end);
+      } else {
+        match = isolate->factory()->NewSubString(subject,
+                                                 match_start,
+                                                 match_end);
+        first = false;
       }
 
-      // If we did not get the maximum number of matches, we can stop here
-      // since there are no matches left.
-      if (num_matches < max_matches) break;
+      if (has_capture) {
+        // 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);
 
-      if (match_start != match_end) {
-        pos = match_end;
+        elements->set(0, *match);
+        for (int i = 1; i <= capture_count; i++) {
+          int start = current_match[i * 2];
+          if (start >= 0) {
+            int end = current_match[i * 2 + 1];
+            ASSERT(start <= end);
+            Handle<String> substring =
+                isolate->factory()->NewSubString(subject, start, end);
+            elements->set(i, *substring);
+          } else {
+            ASSERT(current_match[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));
       } else {
-        pos = match_end + 1;
-        if (pos > subject_length) break;
+        builder->Add(*match);
       }
-    } else if (num_matches == 0) {
-      break;
-    } else {
-      ASSERT_EQ(num_matches, RegExpImpl::RE_EXCEPTION);
-      return RegExpImpl::RE_EXCEPTION;
     }
   }
 
+  if (global_cache.HasException()) return RegExpImpl::RE_EXCEPTION;
+
   if (match_start >= 0) {
+    // Finished matching, with at least one match.
     if (match_end < subject_length) {
       ReplacementStringBuilder::AddSubjectSlice(builder,
                                                 match_end,
                                                 subject_length);
     }
-    SetLastMatchInfoNoCaptures(subject,
-                               last_match_array,
-                               match_start,
-                               match_end);
+
+    RegExpImpl::SetLastMatchInfo(
+        last_match_array, subject, capture_count, NULL);
+
     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 int SearchRegExpMultiple(
-    Isolate* isolate,
-    Handle<String> subject,
-    Handle<JSRegExp> regexp,
-    Handle<JSArray> last_match_array,
-    FixedArrayBuilder* builder,
-    Zone* zone) {
-
-  ASSERT(subject->IsFlat());
-  int registers_per_match = RegExpImpl::IrregexpPrepare(regexp, subject);
-  if (registers_per_match < 0) return RegExpImpl::RE_EXCEPTION;
-
-  int max_matches;
-  int num_registers = RegExpImpl::GlobalOffsetsVectorSize(regexp,
-                                                          registers_per_match,
-                                                          &max_matches);
-  OffsetsVector registers(num_registers, isolate);
-  Vector<int32_t> register_vector(registers.vector(), registers.length());
-
-  int num_matches = RegExpImpl::IrregexpExecRaw(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;
-  bool first = true;
-
-  if (num_matches > 0) {
-    do {
-      int match_start = 0;
-      for (int match_index = 0; match_index < num_matches; match_index++) {
-        int32_t* current_match =
-            &register_vector[match_index * registers_per_match];
-        match_start = current_match[0];
-        builder->EnsureCapacity(kMaxBuilderEntriesPerRegExpMatch);
-        if (match_end < match_start) {
-          ReplacementStringBuilder::AddSubjectSlice(builder,
-                                                    match_end,
-                                                    match_start);
-        }
-        match_end = current_match[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 = current_match[i * 2];
-            if (start >= 0) {
-              int end = current_match[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_match[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));
-        }
-        first = false;
-      }
-
-      // If we did not get the maximum number of matches, we can stop here
-      // since there are no matches left.
-      if (num_matches < max_matches) break;
-
-      if (match_end > match_start) {
-        pos = match_end;
-      } else {
-        pos = match_end + 1;
-        if (pos > subject_length) {
-          break;
-        }
-      }
-
-      num_matches = RegExpImpl::IrregexpExecRaw(regexp,
-                                                subject,
-                                                pos,
-                                                register_vector);
-    } while (num_matches > 0);
-
-    if (num_matches != 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;
-      int last_match_array_size =
-          last_match_capture_count + RegExpImpl::kLastMatchOverhead;
-      last_match_array->EnsureSize(last_match_array_size);
-      AssertNoAllocation no_gc;
-      FixedArray* elements = FixedArray::cast(last_match_array->elements());
-      // We have to set this even though the rest of the last match array is
-      // ignored.
-      RegExpImpl::SetLastCaptureCount(elements, last_match_capture_count);
-      // These are also read without consulting the override.
-      RegExpImpl::SetLastSubject(elements, *subject);
-      RegExpImpl::SetLastInput(elements, *subject);
-      return RegExpImpl::RE_SUCCESS;
-    }
-  }
-  // No matches at all, return failure or exception result directly.
-  return num_matches;
-}
-
-
 // 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.
 RUNTIME_FUNCTION(MaybeObject*, Runtime_RegExpExecMultiple) {
   ASSERT(args.length() == 4);
   HandleScope handles(isolate);
 
   CONVERT_ARG_HANDLE_CHECKED(String, subject, 1);
   if (!subject->IsFlat()) FlattenString(subject);
   CONVERT_ARG_HANDLE_CHECKED(JSRegExp, regexp, 0);
   CONVERT_ARG_HANDLE_CHECKED(JSArray, last_match_info, 2);
   CONVERT_ARG_HANDLE_CHECKED(JSArray, result_array, 3);
 
   ASSERT(last_match_info->HasFastObjectElements());
   ASSERT(regexp->GetFlags().is_global());
   Handle<FixedArray> result_elements;
   if (result_array->HasFastObjectElements()) {
     result_elements =
         Handle<FixedArray>(FixedArray::cast(result_array->elements()));
   }
   if (result_elements.is_null() || result_elements->length() < 16) {
     result_elements = isolate->factory()->NewFixedArrayWithHoles(16);
   }
   FixedArrayBuilder builder(result_elements);
 
-  if (regexp->TypeTag() == JSRegExp::ATOM) {
-    Handle<String> pattern(
-        String::cast(regexp->DataAt(JSRegExp::kAtomPatternIndex)));
-    ASSERT(pattern->IsFlat());
-    if (SearchStringMultiple(isolate, subject, pattern,
-                             last_match_info, &builder)) {
-      return *builder.ToJSArray(result_array);
-    }
-    return isolate->heap()->null_value();
+  int result;
+  if (regexp->CaptureCount() == 0) {
+    result = SearchRegExpMultiple<false>(
+        isolate, subject, regexp, last_match_info, &builder);
+  } else {
+    result = SearchRegExpMultiple<true>(
+        isolate, subject, regexp, last_match_info, &builder);
   }
 
-  ASSERT_EQ(regexp->TypeTag(), JSRegExp::IRREGEXP);
-
-  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,
-                                  isolate->runtime_zone());
-  }
   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);
@@ skipping 9536 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