Avoid extra duplication of substrings during string.replaceAll.

runtime/lib/string.cc

Index: runtime/lib/string.cc
diff --git a/runtime/lib/string.cc b/runtime/lib/string.cc
index 5b450f4a71adf581e2bf87f04e07698e365f575d..5c05ace4b08f43a0e900ffdbd04c429e5bc71554 100644
--- a/runtime/lib/string.cc
+++ b/runtime/lib/string.cc
@@ -103,6 +103,141 @@ DEFINE_NATIVE_ENTRY(StringBase_substringUnchecked, 3) {
 }
 
 
+
+// Return the bitwise-or of all characters in the slice from start to end.
+static uint16_t CharacterLimit(const String& string,
+                               intptr_t start, intptr_t end) {
+  ASSERT(string.IsTwoByteString() ||string.IsExternalTwoByteString());

[zerny-google, 2015/01/20 13:43:11]

Nit: space after ||

[Lasse Reichstein Nielsen, 2015/01/21 10:48:43]

Done.

+  // Maybe do loop unrolling, and handle two uint16_t in a single uint32_t
+  // operation.
+  NoGCScope no_gc;
+  uint16_t result = 0;
+  for (intptr_t i = start; i < end; i++) {
+    result |= TwoByteString::CharAt(string, i);

[Florian Schneider, 2015/01/20 16:39:33]

This should be ExternalTwoByteString::CharAt in the case of an
ExternalTwoByteString. Maybe move this dispatch to outside the loop.

[Lasse Reichstein Nielsen, 2015/01/21 10:48:43]

Done.
Is there a simple way to get the uint16_t* of the data? It seems it's all in
private methods (either through .raw() or using CharAddr).

+  }
+  return result;
+}
+
+
+DEFINE_NATIVE_ENTRY(StringBase_joinReplaceAllResult, 4) {
+  const String& base = String::CheckedHandle(arguments->NativeArgAt(0));
+  GET_NON_NULL_NATIVE_ARGUMENT(GrowableObjectArray,
+                               matches_growable, arguments->NativeArgAt(1));
+  GET_NON_NULL_NATIVE_ARGUMENT(Smi, length_obj, arguments->NativeArgAt(2));
+  GET_NON_NULL_NATIVE_ARGUMENT(Bool, is_onebyte_obj, arguments->NativeArgAt(3));
+
+  intptr_t len = matches_growable.Length();
+  const Array& matches = Array::Handle(matches_growable.data());

[siva, 2015/01/21 00:29:20]

Since 'isolate' is available to the native method use it when creating handles.

[Lasse Reichstein Nielsen, 2015/01/21 10:48:43]

Done in this code. The rest of the file could do it a lot more too.

+
+  const intptr_t kLengthShift = 15;
+  const intptr_t kStartMask = (1 << kLengthShift) - 1;
+
+  const intptr_t length = length_obj.Value();
+  if (length < 0) {
+    Exceptions::ThrowArgumentError(length_obj);
+  }
+
+  // Start out assuming result is one-byte if replacements are.
+  bool is_onebyte = is_onebyte_obj.value();
+  if (is_onebyte) {
+    // If any of the base string slices are not one-byte, the result will be
+    // a two-byte string.
+    if (!base.IsOneByteString() && !base.IsExternalOneByteString()) {
+      Instance& object = Instance::Handle();
+      // Check each slice for one-bytedness.
+      for (intptr_t i = 0; i < len; i++) {
+        object ^= matches.At(i);
+        if (object.IsSmi()) {
+          intptr_t slice_start = Smi::Cast(object).Value();
+          intptr_t slice_end;
+          if (slice_start < 0) {
+            intptr_t bits = -slice_start;
+            slice_start = bits & kStartMask;
+            slice_end = slice_start + (bits >> kLengthShift);
+          } else {
+            i++;
+            object ^= matches.At(i);

[siva, 2015/01/21 00:29:20]

Missing check for if (i < len) here?

[Lasse Reichstein Nielsen, 2015/01/21 10:48:43]

Done.

+            if (!object.IsSmi()) {
+              // Should fail, but just continue and handle the failure later.
+              // This branch isn't called in all cases.
+              is_onebyte = false;
+              break;
+            }
+            slice_end = Smi::Cast(object).Value();
+          }
+          uint16_t char_limit = CharacterLimit(base, slice_start, slice_end);
+          if (char_limit > 0xff) {
+            is_onebyte = false;
+            break;
+          }
+        }
+      }
+    }
+  }
+
+  const intptr_t base_length = base.Length();
+  String& result = String::Handle();
+  if (is_onebyte) {
+    result ^= OneByteString::New(length, Heap::kNew);
+  } else {
+    result ^= TwoByteString::New(length, Heap::kNew);
+  }
+  Instance& object = Instance::Handle();
+  intptr_t writeIndex = 0;
+  for (intptr_t i = 0; i < len; i++) {
+    object ^= matches.At(i);
+    if (object.IsSmi()) {
+      intptr_t slice_start = Smi::Cast(object).Value();
+      intptr_t slice_length = -1;
+      // Slices with limited ranges are stored in a single negative Smi.
+      if (slice_start < 0) {
+        intptr_t bits = -slice_start;
+        slice_start = bits & kStartMask;
+        slice_length = bits >> kLengthShift;
+      } else {
+        i++;
+        if (i < len) {
+          object ^= matches.At(i);
+          if (object.IsSmi()) {
+            intptr_t slice_end = Smi::Cast(object).Value();
+            slice_length = slice_end - slice_start;
+          }
+        }
+      }
+      if (slice_length > 0) {
+        if (0 <= slice_start &&
+            slice_start + slice_length <= base_length &&
+            writeIndex + slice_length <= length) {
+          String::Copy(result, writeIndex,
+                       base, slice_start,
+                       slice_length);
+          writeIndex += slice_length;
+          continue;
+        }
+      }
+      // Either the slice_length was zero,
+      // or the first smi was positive and not followed by another smi,
+      // or the smis were not a valid slice of the base string,
+      // or the slice was too large to fit in the result.
+      // Something is wrong with the matches array!
+      Exceptions::ThrowArgumentError(matches);
+    } else if (object.IsString()) {
+      const String& replacement = String::Cast(object);
+      intptr_t replacement_length = replacement.Length();
+      if (writeIndex + replacement_length > length) {
+        // Invalid input data, either in matches list or the total length.
+        Exceptions::ThrowArgumentError(matches);
+      }
+      String::Copy(result, writeIndex, replacement, 0, replacement_length);
+      writeIndex += replacement_length;
+    }
+  }
+  if (writeIndex < length) {
+    Exceptions::ThrowArgumentError(matches);
+  }
+  return result.raw();

[siva, 2015/01/21 00:29:20]

This function seems to be long, do you think it would make it more readable if
the two 'for' loops are extracted out into helper functions?

[Lasse Reichstein Nielsen, 2015/01/21 10:48:43]

I think I'll move the first loop into a helper method. The second loop is doing
the actual work, so I think it fits here.

+}
+
 DEFINE_NATIVE_ENTRY(OneByteString_substringUnchecked, 3) {
   const String& receiver = String::CheckedHandle(arguments->NativeArgAt(0));
   ASSERT(receiver.IsOneByteString());