Optimize implementation of "replace substrings after offset" utility function to

base/strings/string_util.cc

Index: base/strings/string_util.cc
diff --git a/base/strings/string_util.cc b/base/strings/string_util.cc
index f77034b35c55ad1aac7c408f8362f1e54abffa93..e084cb5597da6cbdcb50d0c3ce958bbc8dbc220e 100644
--- a/base/strings/string_util.cc
+++ b/base/strings/string_util.cc
@@ -556,23 +556,103 @@ string16 FormatBytesUnlocalized(int64 bytes) {
   return base::ASCIIToUTF16(buf);
 }
 
+// Runs in O(n) time in the length of |str|.
 template<class StringType>
 void DoReplaceSubstringsAfterOffset(StringType* str,
-                                    size_t start_offset,
+                                    size_t offset,
                                     const StringType& find_this,
                                     const StringType& replace_with,
                                     bool replace_all) {
-  if ((start_offset == StringType::npos) || (start_offset >= str->length()))
+  DCHECK(!find_this.empty());
+
+  // If the find string doesn't appear, there's nothing to do.
+  offset = str->find(find_this, offset);
+  if (offset == StringType::npos)
     return;
 
-  DCHECK(!find_this.empty());
-  for (size_t offs(str->find(find_this, start_offset));
-      offs != StringType::npos; offs = str->find(find_this, offs)) {
-    str->replace(offs, find_this.length(), replace_with);
-    offs += replace_with.length();
+  // If we're only replacing one instance, there's no need to do anything
+  // complicated.
+  size_t find_length = find_this.length();
+  if (!replace_all) {
+    str->replace(offset, find_length, replace_with);
+    return;
+  }
 
-    if (!replace_all)
-      break;
+  // If the find and replace strings are the same length, we can simply use
+  // replace() on each instance, and finish the entire operation in O(n) time.
+  size_t replace_length = replace_with.length();
+  if (find_length == replace_length) {
+    do {
+      str->replace(offset, find_length, replace_with);
+      offset = str->find(find_this, offset + replace_length);
+    } while (offset != StringType::npos);
+    return;
+  }
+
+  // Since the find and replace strings aren't the same length, a loop like the
+  // one above would be O(n^2) in the worst case, as replace() will shift the
+  // entire remaining string each time.  We need to be more clever to keep
+  // things O(n).
+  //
+  // If we're shortening the string, we can alternate replacements with shifting
+  // forward the intervening characters using memmove().
+  size_t str_length = str->length();
+  if (find_length > replace_length) {
+    size_t write_offset = offset;
+    do {
+      if (replace_length) {
+        str->replace(write_offset, replace_length, replace_with);
+        write_offset += replace_length;
+      }
+      size_t read_offset = offset + find_length;
+      offset = std::min(str->find(find_this, read_offset), str_length);
+      size_t length = offset - read_offset;
+      if (length) {
+        memmove(&(*str)[write_offset], &(*str)[read_offset],
+                length * sizeof(typename StringType::value_type));
+        write_offset += length;
+      }
+    } while (offset < str_length);
+    str->resize(write_offset);
+    return;
+  }
+
+  // We're lengthening the string.  We can use alternating replacements and
+  // memmove() calls like above, but we need to precalculate the final string
+  // length and then expand from back-to-front to avoid overwriting the string
+  // as we're reading it, needing to shift, or having to copy to a second string
+  // temporarily.
+  size_t first_match = offset;
+
+  // First, calculate the final length and resize the string.
+  size_t final_length = str_length;
+  size_t expansion = replace_length - find_length;
+  size_t current_match;
+  do {
+    final_length += expansion;
+    // Minor optimization: save this offset into |current_match|, so that on
+    // exit from the loop, |current_match| will point at the last instance of
+    // the find string, and we won't need to find() it again immediately.
+    current_match = offset;
+    offset = str->find(find_this, offset + find_length);
+  } while (offset != StringType::npos);
+  str->resize(final_length);
+
+  // Now do the replacement loop, working backwards through the string.
+  for (size_t prev_match = str_length, write_offset = final_length; ;
+       current_match = str->rfind(find_this, current_match - 1)) {
+    size_t read_offset = current_match + find_length;
+    size_t length = prev_match - read_offset;
+    if (length) {
+      write_offset -= length;
+      memmove(&(*str)[write_offset], &(*str)[read_offset],
+              length * sizeof(typename StringType::value_type));
+    }
+    write_offset -= replace_length;
+    str->replace(write_offset, replace_length, replace_with);
+    if (current_match == first_match)
+      return;
+    prev_match = current_match;
   }
 }