Avoid extra duplication of substrings during string.replaceAll.

runtime/lib/string_patch.dart

Index: runtime/lib/string_patch.dart
diff --git a/runtime/lib/string_patch.dart b/runtime/lib/string_patch.dart
index 3a1fd711b6cd06e4a46f44ad383d6258a8d47a76..c70f82d9a512305f49f328d6165329012bd7b835 100644
--- a/runtime/lib/string_patch.dart
+++ b/runtime/lib/string_patch.dart
@@ -40,6 +40,11 @@ patch class String {
  * implementations, e.g., _OneByteString.
  */
 class _StringBase {
+  // Constants used by replaceAll encoding of matches.
+  static const int _lengthSize = 11;
+  static const int _maxLengthValue = (1 << _lengthSize) - 1;
+  static const int _maxStartValue = (1 << (30 - _lengthSize)) - 1;

[siva, 2015/01/22 00:08:17]

what are '11' and '30' here? can they be given descriptive names.

[Lasse Reichstein Nielsen, 2015/01/22 08:25:38]

11 is semi-arbitrarily chosen as the size of the length in the encoding of a
slice, so _lengthSize is the descriptive name.
I'll rename it to _lengthBits to make it clear what the unit is.

The 30 is a safe limit of available bits in a negative smi.
I'll give it a name.

+  static const int _lengthMask = _maxLengthValue;
 
   factory _StringBase._uninstantiable() {
     throw new UnsupportedError(
@@ -487,26 +492,140 @@ class _StringBase {
            "${this.substring(match.end)}";
   }
 
+
+  static int _addReplaceSlice(List matches, int start, int end) {
+    int length = end - start;
+    if (length > 0) {
+      if (length <= _maxLengthValue && start <= _maxStartValue) {
+        matches.add(-((start << _lengthSize) | length));
+      } else {
+        matches.add(start);
+        matches.add(end);
+      }
+    }
+    return length;
+  }
+
   String replaceAll(Pattern pattern, String replacement) {
-    if (pattern is! Pattern) {
-      throw new ArgumentError("${pattern} is not a Pattern");
+    if (pattern == null) throw new ArgumentError.notNull("pattern");
+    if (replacement == null) throw new ArgumentError.notNull("replacement");
+    List matches = [];
+    int length = 0;
+    int replacementLength = replacement.length;
+    int startIndex = 0;
+    if (replacementLength == 0) {
+      int count = 0;
+      for (Match match in pattern.allMatches(this)) {
+        length += _addReplaceSlice(matches, startIndex, match.start);
+        startIndex = match.end;
+      }
+    } else {
+      for (Match match in pattern.allMatches(this)) {
+        length += _addReplaceSlice(matches, startIndex, match.start);
+        matches.add(replacement);
+        length += replacementLength;
+        startIndex = match.end;
+      }
     }
-    if (replacement is! String) {
-      throw new ArgumentError(
-          "${replacement} is not a String or Match->String function");
+    length += _addReplaceSlice(matches, startIndex, this.length);
+    bool replacementIsOneByte = (replacement is _OneByteString) ||
+                                (replacement is _ExternalOneByteString);
+    if (replacementIsOneByte && length < 500) {

[siva, 2015/01/22 00:08:17]

document this magic constant as
static const int _xxxxxxValue = 500;
in this class.

[Lasse Reichstein Nielsen, 2015/01/22 08:25:38]

Done:   
static const int _maxJoinReplaceOneByteStringLength = 500;

I guess it could be shorter, but not without loosing precision :)

+      // TODO(lrn): Is there a cut-off point, or is runtime always faster?
+      bool thisIsOneByte = (this is _OneByteString) ||
+                           (this is _ExternalOneByteString);
+      if (replacementIsOneByte && thisIsOneByte) {
+        return _joinReplaceAllOneByteResult(this, matches, length);
+      }
     }
-    StringBuffer buffer = new StringBuffer();
-    int startIndex = 0;
-    for (Match match in pattern.allMatches(this)) {
-      buffer..write(this.substring(startIndex, match.start))
-            ..write(replacement);
-      startIndex = match.end;
+    return _joinReplaceAllResult(this, matches, length,
+                                 replacementIsOneByte);
+  }
+
+  /**
+   * As [_joinReplaceAllResult], but knowing that the result
+   * is always a [_OneByteString].
+   */
+  static String _joinReplaceAllOneByteResult(String base,
+                                             List matches,
+                                             int length) {
+    _OneByteString result = _OneByteString._allocate(length);
+    int writeIndex = 0;
+    for (int i = 0; i < matches.length; i++) {
+      var entry = matches[i];
+      if (entry is _Smi) {
+        int sliceStart = entry;
+        int sliceEnd;
+        if (sliceStart < 0) {
+          int bits = -sliceStart;
+          int sliceLength = bits & _lengthMask;
+          sliceStart = bits >> _lengthSize;
+          sliceEnd = sliceStart + sliceLength;
+        } else {
+          i++;
+          // This function should only be called with valid matches lists.
+          // If the list is short, or sliceEnd is not an integer, one of
+          // the next few lines will throw anyway.
+          assert(i < matches.length);
+          sliceEnd = matches[i];
+        }
+        for (int j = sliceStart; j < sliceEnd; j++) {
+          result._setAt(writeIndex++, base.codeUnitAt(j));
+        }
+      } else {
+        // Replacement is a one-byte string.
+        String replacement = entry;
+        for (int j = 0; j < replacement.length; j++) {
+          result._setAt(writeIndex++, replacement.codeUnitAt(j));
+        }
+      }
     }
-    return (buffer..write(this.substring(startIndex))).toString();
+    assert(writeIndex == length);
+    return result;
   }
 
+  /**
+   * Combine the results of a [replaceAll] match into a new string.
+   *
+   * The [matches] lists contains Smi index pairs representing slices of
+   * [base] and [String]s to be put in between the slices.
+   *
+   * The total [length] of the resulting string is known, as is
+   * whether the replacement strings are one-byte strings.
+   * If they are, then we have to check the base string slices to know
+   * whether the result must be a one-byte string.
+   */
+  static String _joinReplaceAllResult(String base, List matches, int length,
+                                      bool replacementStringsAreOneByte)
+      native "StringBase_joinReplaceAllResult";
+
   String replaceAllMapped(Pattern pattern, String replace(Match match)) {
-    return splitMapJoin(pattern, onMatch: replace);
+    if (pattern == null) throw new ArgumentError.notNull("pattern");
+    if (replace == null) throw new ArgumentError.notNull("replace");
+    List matches = [];
+    int length = 0;
+    int startIndex = 0;
+    bool replacementStringsAreOneByte = true;
+    for (Match match in pattern.allMatches(this)) {
+      length += _addReplaceSlice(matches, startIndex, match.start);
+      String replacement = replace(match).toString();
+      matches.add(replacement);
+      length += replacement.length;
+      replacementStringsAreOneByte = replacementStringsAreOneByte &&
+          (replacement is _OneByteString ||
+           replacement is _ExternalOneByteString);
+      startIndex = match.end;
+    }
+    length += _addReplaceSlice(matches, startIndex, this.length);
+    if (replacementStringsAreOneByte && length < 500) {
+      bool thisIsOneByte = (this is _OneByteString) ||
+                           (this is _ExternalOneByteString);
+      if (thisIsOneByte) {
+        return _joinReplaceAllOneByteResult(this, matches, length);
+      }
+    }
+    return _joinReplaceAllResult(this, matches, length,
+                                 replacementStringsAreOneByte);
   }
 
   static String _matchString(Match match) => match[0];