Faster string.replace with regexp pattern.

src/runtime.cc

 // Copyright 2006-2008 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 1162 matching lines @@
   ASSERT(args.length() == 1);
   uint32_t code;
   if (Array::IndexFromObject(args[0], &code)) {
     if (code <= 0xffff) {
       return Heap::LookupSingleCharacterStringFromCode(code);
     }
   }
   return Heap::empty_string();
 }
 
+class ReplacementStringBuilder {

[Erik Corry, 2009/03/12 10:13:00]

I think you should use StringBuilderConcatHelper instead of Cons Strings.

[Lasse Reichstein, 2009/03/13 08:36:51]

Done.

+ public:
+  ReplacementStringBuilder() : string_() {}
+
+  void Add(Handle<String> string) {
+    StringShape shape(*string);
+    if (string->length(shape) > 0) {
+      if (string_.is_null()) {
+        string_ = string;
+      } else {
+        string_ =
+            Factory::NewConsString(string_, StringShape(*string_),
+                                   string, shape);
+      }
+    }
+  }
+
+  Handle<String> ToString() {
+    if (string_.is_null()) {
+      return Factory::empty_string();
+    }
+    return string_;
+  }
+ private:
+  Handle<String> string_;
+};
+
+
+class CompiledReplacement {
+ public:
+  CompiledReplacement(Handle<String> replacement, int capture_count)
+      : parts_(1), replacement_substrings_(0) {
+    ParseReplacement(replacement, capture_count);

[Erik Corry, 2009/03/12 10:13:00]

Nontrivial work shouldn't be in constructors.

[Lasse Reichstein, 2009/03/13 08:36:51]

Done.

+  }
+  void Apply(ReplacementStringBuilder* builder,
+             int match_from,
+             int match_to,
+             Handle<String> subject,
+             Handle<JSArray> last_match_info) {
+    for (int i = 0, n = parts_.length(); i < n; i++) {
+      ReplacementPart part = parts_[i];
+      switch (part.tag) {
+        case SUBJECT_MATCH:
+          builder->Add(Factory::NewStringSlice(subject, match_from, match_to));
+          break;
+        case SUBJECT_PREFIX:
+          builder->Add(Factory::NewStringSlice(subject, 0, match_from));
+          break;
+        case SUBJECT_SUFFIX: {
+          int length = subject->length();
+          builder->Add(Factory::NewStringSlice(subject, match_to, length));
+          break;
+        }
+        case SUBJECT_CAPTURE: {
+          int capture = part.data;
+          FixedArray* match_info = last_match_info->elements();

[Erik Corry, 2009/03/12 10:13:00]

Move outside loop?  Actually, you should move this outside the function
completely so you can get it outside the /g loop.

[Lasse Reichstein, 2009/03/13 08:36:51]

As commented later, it can't be moved that far out.
It could be moved out of this loop, but then it would be computed even when it's
not used (e.g., replacing with a constant string).

+          int from = RegExpImpl::GetCapture(match_info, capture * 2);
+          int to = RegExpImpl::GetCapture(match_info, capture * 2 + 1);
+          builder->Add(Factory::NewStringSlice(subject, from, to));
+          break;
+        }
+        case REPLACEMENT_SUBSTRING:
+          builder->Add(replacement_substrings_[part.data]);
+          break;
+        default:
+          UNREACHABLE();
+      }
+    }
+  }
+ private:
+  enum PartType {
+    SUBJECT_MATCH = -1,

[Erik Corry, 2009/03/12 10:13:00]

Subject match seems like a special case of subject capture.

[Lasse Reichstein, 2009/03/13 08:36:51]

True. Slightly faster to implement since I already have the match start and end
indices computed. Probably not worth it. I'll remove it for now.

+    SUBJECT_PREFIX = -2,
+    SUBJECT_SUFFIX = -3,
+    SUBJECT_CAPTURE = -4,
+    REPLACEMENT_SUBSTRING = -5

[Erik Corry, 2009/03/12 10:13:00]

I'd prefer these to be positive and the offsets negative.  That way the switch
is with positive values which seems like the more common case for the C++
compiler implementer.

[Lasse Reichstein, 2009/03/13 08:36:51]

Done.

+  };
+
+  struct ReplacementPart {
+    // If tag >= 0 then it is the start index of a substring of the replacement
+    // pattern.
+    ReplacementPart(int tag, int data)
+        : tag(tag), data(data) {}
+    int tag;
+    int data;

[Erik Corry, 2009/03/12 10:13:00]

'data' is too generic a name, there's no comment to explain what it's for.

[Lasse Reichstein, 2009/03/13 08:36:51]

Comments added.

+  };
+
+  template<typename Char>
+  static void Parse(ZoneList<ReplacementPart>* parts,
+                    Vector<Char> characters,
+                    int capture_count) {
+    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];
+        switch (c2) {
+        case '$':
+          if (i > last) {
+            // Up to and including the first "$".
+            parts->Add(ReplacementPart(last, next_index));
+            last = next_index + 1;  // Continue after the second "$".
+          } else {
+            last = next_index;  // Continue with the second "$".
+          }
+          i = next_index;
+          break;
+        case '`':
+          if (i > last) {
+            parts->Add(ReplacementPart(last, i));

[Erik Corry, 2009/03/12 10:13:00]

Perhaps parts->Add could check for last == i to save you doing it in 4 out of 5
places.

[Lasse Reichstein, 2009/03/13 08:36:51]

Parts is just a ZoneList, and this is a self-contained static function, so I
don't think the overhead of moving those tests somewhere else is worth it.

+          }
+          parts->Add(ReplacementPart(SUBJECT_PREFIX, 0));
+          i = next_index;
+          last = i + 1;
+          break;
+        case '\'':
+          if (i > last) {
+            parts->Add(ReplacementPart(last, i));
+          }
+          parts->Add(ReplacementPart(SUBJECT_SUFFIX, 0));
+          i = next_index;
+          last = i + 1;
+          break;
+        case '&':
+          if (i > last) {
+            parts->Add(ReplacementPart(last, i));
+          }
+          parts->Add(ReplacementPart(SUBJECT_MATCH, 0));
+          i = next_index;
+          last = i + 1;
+          break;
+        case '0':

[Erik Corry, 2009/03/12 10:13:00]

Are $0 and $04 allowed?  Should $0 be taken verbatim?

[Lasse Reichstein, 2009/03/13 08:36:51]

Yes and yes.

+        case '1':
+        case '2':
+        case '3':
+        case '4':
+        case '5':
+        case '6':
+        case '7':
+        case '8':
+        case '9': {
+          int capture_ref = c2 - '0';
+          if (capture_ref > capture_count) {
+            i = next_index;
+            continue;
+          }
+          int second_digit_index = next_index + 1;
+          if (second_digit_index < length) {
+            // Peek ahead to see if we have two digits.
+            Char c3 = characters[second_digit_index];
+            if ('0' <= c3 && c3 <= '9') {  // Double digits.
+              int double_digit_ref = capture_ref * 10 + c3 - '0';
+              if (double_digit_ref <= capture_count) {
+                next_index = second_digit_index;
+                capture_ref = double_digit_ref;
+              }
+            }
+          }
+          if (capture_ref > 0) {
+            if (i > last) {
+              parts->Add(ReplacementPart(last, i));
+            }
+            parts->Add(ReplacementPart(SUBJECT_CAPTURE, capture_ref));
+            last = next_index + 1;
+          }
+          i = next_index;
+          break;
+        }
+        default:

[Erik Corry, 2009/03/12 10:13:00]

Should $F00 replace with $FOO or FOO?

[Lasse Reichstein, 2009/03/13 08:36:51]

With "$F00".

+          i = next_index;
+          break;
+        }
+      }
+    }
+    if (length > last) {
+      parts->Add(ReplacementPart(last, length));
+    }
+  }
+
+  void ParseReplacement(Handle<String> replacement, int capture_count) {
+    StringShape shape(*replacement);
+    ASSERT(replacement->IsFlat(shape));
+    if (shape.IsAsciiRepresentation()) {
+      Parse(&parts_, replacement->ToAsciiVector(), capture_count);
+    } else {
+      ASSERT(shape.IsTwoByteRepresentation());
+      Parse(&parts_, replacement->ToUC16Vector(), capture_count);
+    }
+    // Find substrings of replacement string and create them as String objcts..
+    int 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 end = parts_[i].data;
+        replacement_substrings_.Add(Factory::NewStringSlice(replacement,
+                                                            tag,
+                                                            end));
+        parts_[i].tag = REPLACEMENT_SUBSTRING;
+        parts_[i].data = index;
+        index++;
+      }
+    }
+  }
+
+  ZoneList<ReplacementPart> parts_;
+  ZoneList<Handle<String> > replacement_substrings_;
+};
+
+
+static Object* StringReplaceRegExpWithString(String* subject,
+                                             JSRegExp* regexp,
+                                             String* replacement,
+                                             JSArray* last_match_info) {
+  ASSERT(subject->IsFlat(StringShape(subject)));
+  ASSERT(replacement->IsFlat(StringShape(replacement)));
+
+  HandleScope handles;
+
+  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();
+
+  // CompiledReplacement uses zone allocation.
+  ZoneScope zone(DELETE_ON_EXIT);
+  CompiledReplacement compiled_replacement(replacement_handle, capture_count);
+  ReplacementStringBuilder builder;
+  bool is_global = regexp_handle->GetFlags().is_global();
+
+  // Index of end of last match.
+  int prev = 0;
+
+  do {
+    ASSERT(last_match_info_handle->HasFastElements());
+    FixedArray* match_data = last_match_info_handle->elements();

[Erik Corry, 2009/03/12 10:13:00]

Not using a handle is a little dodgy.  If you move this outside the loop you
don't have to worry about the Handle copying overhead.

[Lasse Reichstein, 2009/03/13 08:36:51]

Won't work. The loop might be preempted (since it calls RegExps) and some other
code might extend the last_match_info array, so it's not safe to retain a
reference to the current backing FixedArray. We need to extract it on every
iteration.

To avoid creating a handle for every iteration, I just extract the pointer and
use it immediately.

[Erik Corry, 2009/03/13 09:12:34]

If you retain a reference to the old FixedArray then it will not be collected
and you can write your captures to it.  The static properties on RegExp will not
reflect your changes but if you are using regexps in multiple threads that is
not unexpected.  But we can save that for another afsnit.

+    ASSERT_EQ(capture_count * 2 + 2,
+              Smi::cast(
+                  match_data->get(RegExpImpl::kLastCaptureCount))->value());
+
+    int start = RegExpImpl::GetCapture(match_data, 0);
+    int end = RegExpImpl::GetCapture(match_data, 1);
+
+    if (prev < start) {
+      builder.Add(Factory::NewStringSlice(subject_handle, prev, start));
+    }
+    compiled_replacement.Apply(&builder,
+                               start,
+                               end,
+                               subject_handle,
+                               last_match_info_handle);
+    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;
+    }
+
+    match = RegExpImpl::Exec(regexp_handle,
+                             subject_handle,
+                             next,
+                             last_match_info_handle);
+    if (match.is_null()) {
+      return Failure::Exception();
+    }
+  } while (!match->IsNull());
+
+  if (prev < length) {
+    builder.Add(Factory::NewStringSlice(subject_handle, prev, length));
+  }
+
+  return *(builder.ToString());
+}
+
+
+static Object* Runtime_StringReplaceRegExpWithString(Arguments args) {
+  ASSERT(args.length() == 4);
+
+  CONVERT_CHECKED(String, subject, args[0]);
+  StringShape subject_shape(subject);
+  if (!subject->IsFlat(subject_shape)) {
+    Object* flat_subject = subject->TryFlatten(subject_shape);
+    if (flat_subject->IsFailure()) {
+      return flat_subject;
+    }
+    subject = String::cast(flat_subject);
+  }
+
+  CONVERT_CHECKED(String, replacement, args[2]);
+  StringShape replacement_shape(replacement);
+  if (!replacement->IsFlat(replacement_shape)) {
+    Object* flat_replacement = replacement->TryFlatten(replacement_shape);
+    if (flat_replacement->IsFailure()) {
+      return flat_replacement;
+    }
+    replacement = String::cast(flat_replacement);
+  }
+
+  CONVERT_CHECKED(JSRegExp, regexp, args[1]);
+  CONVERT_CHECKED(JSArray, last_match_info, args[3]);

[Erik Corry, 2009/03/12 10:13:00]

You need to check here that the last_match_info has fast elements and you need
to check that is is big enough somewhere.

[Lasse Reichstein, 2009/03/13 08:36:51]

I only ever use last_match_info after having executed a regular expression
successfully. That should ensure the size as well as check that the array has
fast elements.
But yes, failing fast is a good thing, so I'll add an extra test here.

+
+  return StringReplaceRegExpWithString(subject,
+                                       regexp,
+                                       replacement,
+                                       last_match_info);
+}
+
+
 
 // Cap on the maximal shift in the Boyer-Moore implementation. By setting a
 // limit, we can fix the size of tables.
 static const int kBMMaxShift = 0xff;
 // Reduce alphabet to this size.
 static const int kBMAlphabetSize = 0x100;
 // For patterns below this length, the skip length of Boyer-Moore is too short
 // to compensate for the algorithmic overhead compared to simple brute force.
 static const int kBMMinPatternLength = 5;
 
@@ skipping 5004 matching lines @@
   } else {
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     Counters::gc_last_resort_from_js.Increment();
     Heap::CollectAllGarbage();
   }
 }
 
 
 } }  // namespace v8::internal