Avoid extra duplication of substrings during string.replaceAll.

runtime/lib/string.cc

 // Copyright (c) 2011, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/bootstrap_natives.h"
 
 #include "include/dart_api.h"
 #include "vm/exceptions.h"
 #include "vm/dart_api_impl.h"
 #include "vm/isolate.h"
@@ skipping 85 matching lines @@
   const String& receiver = String::CheckedHandle(arguments->NativeArgAt(0));
   GET_NON_NULL_NATIVE_ARGUMENT(Smi, start_obj, arguments->NativeArgAt(1));
   GET_NON_NULL_NATIVE_ARGUMENT(Smi, end_obj, arguments->NativeArgAt(2));
 
   intptr_t start = start_obj.Value();
   intptr_t end = end_obj.Value();
   return String::SubString(receiver, start, (end - start));
 }
 
 
+
+// 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());
   GET_NON_NULL_NATIVE_ARGUMENT(Smi, start_obj, arguments->NativeArgAt(1));
   GET_NON_NULL_NATIVE_ARGUMENT(Smi, end_obj, arguments->NativeArgAt(2));
 
   const intptr_t start = start_obj.Value();
   const intptr_t end = end_obj.Value();
   return OneByteString::New(receiver, start, end - start, Heap::kNew);
 }
@@ skipping 258 matching lines @@
       ? String::Handle(OneByteString::New(length_value, Heap::kNew))
       : String::Handle(TwoByteString::New(length_value, Heap::kNew));
   NoGCScope no_gc;
 
   uint16_t* data_position = reinterpret_cast<uint16_t*>(codeUnits.DataAddr(0));
   String::Copy(result, 0, data_position, length_value);
   return result.raw();
 }
 
 }  // namespace dart