Avoid extra duplication of substrings during string.replaceAll.

runtime/lib/string_patch.dart

 // Copyright (c) 2012, 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.
 
 patch class String {
   /* patch */ factory String.fromCharCodes(Iterable<int> charCodes,
                                            [int start = 0, int end]) {
     return _StringBase.createFromCharCodes(charCodes, start, end);
   }
 
@@ skipping 22 matching lines @@
                                                    {String defaultValue})
       native "String_fromEnvironment";
 }
 
 
 /**
  * [_StringBase] contains common methods used by concrete String
  * implementations, e.g., _OneByteString.
  */
 class _StringBase {
+  // Constants used by replaceAll encoding of matches.
+  static const int _lengthShift = 15;
+  static const int _maxStartValue = (1 << _lengthShift) - 1;
+  static const int _maxLengthValue = (1 << (30 - _lengthShift)) - 1;
+  static const int _startMask = _maxStartValue;
 
   factory _StringBase._uninstantiable() {
     throw new UnsupportedError(
         "_StringBase can't be instaniated");
   }
 
   Type get runtimeType => String;
 
   int get hashCode native "String_getHashCode";
 
@@ skipping 428 matching lines @@
         startIndex == 0 ? pattern.allMatches(this).iterator
                         : pattern.allMatches(this, startIndex).iterator;
     if (!iterator.moveNext()) return this;
     Match match = iterator.current;
     return "${this.substring(0, match.start)}"
            "$replacement"
            "${this.substring(match.end)}";
   }
 
   String replaceAll(Pattern pattern, String replacement) {
-    if (pattern is! Pattern) {
-      throw new ArgumentError("${pattern} is not a Pattern");

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

Is it OK that we no longer have an explicit ArgumentError here and below?

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

Almost. I'll add back a check for "null", but we shouldn't be checking that the
argument has the type that its type annotation requires - the analyzer is there
to warn if you use it incorrectly.

+    List matches = [];
+    int length = 0;
+    int replacementLength = replacement.length;
+    int startIndex = 0;
+    if (replacementLength == 0) {
+      for (Match match in pattern.allMatches(this)) {
+        int matchStart = match.start;
+        int preMatchLength = match.start - startIndex;
+        if (preMatchLength > 0) {
+          if (startIndex <= _maxStartValue &&
+              preMatchLength <= _maxLengthValue) {
+            matches.add(-(startIndex | preMatchLength << _lengthShift));

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

Nit: add parens around <<

Also, does compacting the matches array like this have any measurable payoff?

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

Done.
I see ~5% improvement on a small/micro benchmark.
It should be simple to turn it off and see the difference.

+          } else {
+            matches.add(startIndex);
+            matches.add(matchStart);
+          }
+          length += preMatchLength;
+        }
+        startIndex = match.end;
+      }
+    } else {
+      for (Match match in pattern.allMatches(this)) {
+        int matchStart = match.start;
+        int preMatchLength = match.start - startIndex;
+        if (preMatchLength > 0) {
+          if (startIndex <= _maxStartValue &&
+              preMatchLength <= _maxLengthValue) {
+            matches.add(-(startIndex | preMatchLength << _lengthShift));
+          } else {
+            matches.add(startIndex);
+            matches.add(matchStart);
+          }
+          length += preMatchLength;
+        }
+        matches.add(replacement);
+        length += replacementLength;
+        startIndex = match.end;
+      }
     }
-    if (replacement is! String) {
-      throw new ArgumentError(
-          "${replacement} is not a String or Match->String function");
+    if (startIndex < this.length) {
+      matches.add(startIndex);
+      matches.add(this.length);
+      length += this.length - startIndex;
     }
-    StringBuffer buffer = new StringBuffer();
+    bool replacementIsOneByte = (replacement is _OneByteString) ||
+                                (replacement is _ExternalOneByteString);
+    bool thisIsOneByte = (this is _OneByteString) ||
+                         (this is _ExternalOneByteString);
+    if (replacementIsOneByte && thisIsOneByte) {
+      _joinReplaceAllOneByteResult(this, matches, length);
+    }
+    return _joinReplaceAllResult(this, matches, length,

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

Would it make sense to implement the 'this' two-byte case also in Dart instead
of going to C++?

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

The one-byte case actually turns out to be slower in some cases, so I'll limit
it to small strings. I'll see if I can find out why.

There is no TwoByteString._allocate and _setCharAt functions, so we can't create
a TwoByteString in Dart code like we can for OneByteString.

+                                 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;
+          sliceStart = bits & _startMask;
+          sliceEnd = sliceStart + (bits >> _lengthShift);
+        } else {
+          i++;

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

This is really dicey, 'i' is being incremented and there is no check if it is
still '< matches.length', if it is expected to be less then at least document
that and assert that it is less.

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

Adding assert.
This function should only be called from the one above, where we only build
valid matches lists.
If someone calls it with bad data, it's OK to just die at the array access
instead of doing the i < matches.length check first.

+          sliceEnd = matches[i];
+        }
+        for (int j = sliceStart; j < sliceEnd; j++) {
+          result._setAt(writeIndex++, base.codeUnitAt(j));
+        }
+      } else {
+        _OneByteString replacement = entry;
+        for (int j = 0; j < replacement.length; j++) {
+          result._setAt(writeIndex++, replacement.codeUnitAt(j));
+        }
+      }
+    }
+    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)) {
+    List matches = [];
+    int length = 0;
     int startIndex = 0;
+    bool replacementStringsAreOneByte = true;
     for (Match match in pattern.allMatches(this)) {
-      buffer..write(this.substring(startIndex, match.start))
-            ..write(replacement);
+      int matchStart = match.start;
+      int preMatchLength = match.start - startIndex;
+      if (preMatchLength > 0) {
+        if (startIndex <= _maxStartValue &&
+            preMatchLength <= _maxLengthValue) {
+          matches.add(-(startIndex | preMatchLength << _lengthShift));
+        } else {
+          matches.add(startIndex);
+          matches.add(matchStart);
+        }
+        length += preMatchLength;
+      }
+      String replacement = replace(match);
+      matches.add(replacement);
+      length += replacement.length;
+      replacementStringsAreOneByte = replacementStringsAreOneByte &&
+          (replacement is _OneByteString ||
+           replacement is _ExternalOneByteString);
       startIndex = match.end;
     }
-    return (buffer..write(this.substring(startIndex))).toString();
-  }
-
-  String replaceAllMapped(Pattern pattern, String replace(Match match)) {
-    return splitMapJoin(pattern, onMatch: replace);
+    if (startIndex < this.length) {
+      matches.add(startIndex);
+      matches.add(this.length);
+      length += this.length - startIndex;
+    }
+    bool thisIsOneByte = (this is _OneByteString) ||
+                         (this is _ExternalOneByteString);
+    if (replacementStringsAreOneByte && thisIsOneByte) {
+      _joinReplaceAllOneByteResult(this, matches, length);
+    }
+    return _joinReplaceAllResult(this, matches, length,
+                                 replacementStringsAreOneByte);
   }
 
   static String _matchString(Match match) => match[0];
   static String _stringIdentity(String string) => string;
 
   String _splitMapJoinEmptyString(String onMatch(Match match),
                                   String onNonMatch(String nonMatch)) {
     // Pattern is the empty string.
     StringBuffer buffer = new StringBuffer();
     int length = this.length;
@@ skipping 555 matching lines @@
 class _CodeUnits extends Object with ListMixin<int>,
                                      UnmodifiableListMixin<int> {
   /** The string that this is the code units of. */
   String _string;
 
   _CodeUnits(this._string);
 
   int get length => _string.length;
   int operator[](int i) => _string.codeUnitAt(i);
 }