Reviewed by Darin.
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 15 Sep 2004 00:16:34 +0000 (00:16 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 15 Sep 2004 00:16:34 +0000 (00:16 +0000)
<rdar://problem/3794735> Gmail- sending a very long message with Safari is so slow it seems like a hang

* kjs/string_object.cpp:
        (StringProtoFuncImp::call): Replaced implementation of replace()
method with function below...
(replace): In order to avoid excessive allocation and copying,
figure out the ranges of the original string and replacement
strings to be assembled, instead of constantly creating new
strings at each substitution. The old behavior is basically O(N^2)
for a global replace on a pattern that matches many places in the
string.
        (regExpIsGlobal): Helper function for the above.
        (expandSourceRanges): ditto
        (pushSourceRange): ditto
        (expandReplacements): ditto
        (pushReplacement): ditto
        * kjs/ustring.cpp:
(KJS::UString::spliceSubstringsWithSeparators): New method that
pieces together substring ranges of this string together with
specified separators, all at one go.
        * kjs/ustring.h:
        (KJS::UString::Range::Range): Added new helper class to represent
substring choices.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@7564 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JavaScriptCore/ChangeLog
JavaScriptCore/kjs/string_object.cpp
JavaScriptCore/kjs/ustring.cpp
JavaScriptCore/kjs/ustring.h

index 9d560066d12a18f1ec7a000ec0eb365aa246bc4f..744a4f8cfa774c2a122dfc2e03674c1682df6c03 100644 (file)
@@ -1,3 +1,31 @@
+2004-09-13  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Darin.
+
+       <rdar://problem/3794735> Gmail- sending a very long message with Safari is so slow it seems like a hang
+        
+       * kjs/string_object.cpp:
+        (StringProtoFuncImp::call): Replaced implementation of replace()
+       method with function below...
+       (replace): In order to avoid excessive allocation and copying,
+       figure out the ranges of the original string and replacement
+       strings to be assembled, instead of constantly creating new
+       strings at each substitution. The old behavior is basically O(N^2)
+       for a global replace on a pattern that matches many places in the
+       string.
+        (regExpIsGlobal): Helper function for the above.
+        (expandSourceRanges): ditto
+        (pushSourceRange): ditto
+        (expandReplacements): ditto
+        (pushReplacement): ditto
+        * kjs/ustring.cpp:
+       (KJS::UString::spliceSubstringsWithSeparators): New method that
+       pieces together substring ranges of this string together with
+       specified separators, all at one go.
+        * kjs/ustring.h:
+        (KJS::UString::Range::Range): Added new helper class to represent
+       substring choices.
+
 2004-09-14  Maciej Stachowiak  <mjs@apple.com>
 
         Reviewed by Darin.
index 16d68776d3f3b9f0bd262a04fc43fc2644bde233..7d4abe48090bafe6727ea8e6a20669730389b4ed 100644 (file)
@@ -170,6 +170,165 @@ bool StringProtoFuncImp::implementsCall() const
   return true;
 }
 
+static inline bool regExpIsGlobal(RegExpImp *regExp, ExecState *exec)
+{
+    Value globalProperty = regExp->get(exec,"global");
+    return globalProperty.type() != UndefinedType && globalProperty.toBoolean(exec);
+}
+
+static inline void expandSourceRanges(UString::Range * & array, int& count, int& capacity)
+{
+  int newCapacity;
+  if (capacity == 0) {
+    newCapacity = 16;
+  } else {
+    newCapacity = capacity * 2;
+  }
+
+  UString::Range *newArray = new UString::Range[newCapacity];
+  for (int i = 0; i < count; i++) {
+    newArray[i] = array[i];
+  }
+
+  delete [] array;
+
+  capacity = newCapacity;
+  array = newArray;
+}
+
+static void pushSourceRange(UString::Range * & array, int& count, int& capacity, UString::Range range)
+{
+  if (count + 1 > capacity)
+    expandSourceRanges(array, count, capacity);
+
+  array[count] = range;
+  count++;
+}
+
+static inline void expandReplacements(UString * & array, int& count, int& capacity)
+{
+  int newCapacity;
+  if (capacity == 0) {
+    newCapacity = 16;
+  } else {
+    newCapacity = capacity * 2;
+  }
+
+  UString *newArray = new UString[newCapacity];
+  for (int i = 0; i < count; i++) {
+    newArray[i] = array[i];
+  }
+  
+  delete [] array;
+
+  capacity = newCapacity;
+  array = newArray;
+}
+
+static void pushReplacement(UString * & array, int& count, int& capacity, UString replacement)
+{
+  if (count + 1 > capacity)
+    expandReplacements(array, count, capacity);
+
+  array[count] = replacement;
+  count++;
+}
+
+static inline UString substituteBackreferences(const UString &replacement, const UString &source, int **ovector, RegExp *reg)
+{
+  UString substitutedReplacement = replacement;
+
+  bool converted;
+
+  for (int i = 0; (i = substitutedReplacement.find(UString("$"), i)) != -1; i++) {
+    if (i+1 < substitutedReplacement.size() && substitutedReplacement[i+1] == '$') {  // "$$" -> "$"
+      substitutedReplacement = substitutedReplacement.substr(0,i) + "$" + substitutedReplacement.substr(i+2);
+      continue;
+    }
+    // Assume number part is one char exactly
+    unsigned long backrefIndex = substitutedReplacement.substr(i+1,1).toULong(&converted, false /* tolerate empty string */);
+    if (converted && backrefIndex <= (unsigned)reg->subPatterns()) {
+      int backrefStart = (*ovector)[2*backrefIndex];
+      int backrefLength = (*ovector)[2*backrefIndex+1] - backrefStart;
+      substitutedReplacement = substitutedReplacement.substr(0,i)
+        + source.substr(backrefStart, backrefLength)
+        + substitutedReplacement.substr(i+2);
+      i += backrefLength - 1; // -1 offsets i++
+    }
+  }
+
+  return substitutedReplacement;
+}
+
+static Value replace(ExecState *exec, const UString &source, const Value &pattern, const Value &replacement)
+{
+  if (pattern.type() == ObjectType && pattern.toObject(exec).inherits(&RegExpImp::info)) {
+    RegExpImp* imp = static_cast<RegExpImp *>( pattern.toObject(exec).imp() );
+    RegExp *reg = imp->regExp();
+    bool global = regExpIsGlobal(imp, exec);
+
+    RegExpObjectImp* regExpObj = static_cast<RegExpObjectImp*>(exec->lexicalInterpreter()->builtinRegExp().imp());
+
+    UString replacementString = replacement.toString(exec);
+
+    int matchIndex = 0;
+    int lastIndex = 0;
+    int startPosition = 0;
+
+    UString::Range *sourceRanges = 0;
+    int sourceRangeCount = 0;
+    int sourceRangeCapacity = 0;
+    UString *replacements = 0;
+    int replacementCount = 0;
+    int replacementCapacity = 0;
+
+    // This is either a loop (if global is set) or a one-way (if not).
+    do {
+      int **ovector = regExpObj->registerRegexp( reg, source );
+      UString matchString = reg->match(source, startPosition, &matchIndex, ovector);
+      regExpObj->setSubPatterns(reg->subPatterns());
+      if (matchIndex == -1)
+        break;
+      int matchLen = matchString.size();
+
+      pushSourceRange(sourceRanges, sourceRangeCount, sourceRangeCapacity, UString::Range(lastIndex, matchIndex - lastIndex));
+
+      UString substitutedReplacement = substituteBackreferences(replacementString, source, ovector, reg);
+      pushReplacement(replacements, replacementCount, replacementCapacity, substitutedReplacement);
+
+      lastIndex = matchIndex + matchLen;
+      startPosition = lastIndex;
+
+      // special case of empty match
+      if (matchLen == 0) {
+        startPosition++;
+        if (startPosition > source.size())
+          break;
+      }
+    } while (global);
+
+    if (lastIndex < source.size())
+      pushSourceRange(sourceRanges, sourceRangeCount, sourceRangeCapacity, UString::Range(lastIndex, source.size() - lastIndex));
+
+    UString result = source.spliceSubstringsWithSeparators(sourceRanges, sourceRangeCount, replacements, replacementCount);
+
+    delete [] sourceRanges;
+    delete [] replacements;
+
+    return String(result);
+  } else { // First arg is a string
+    UString patternString = pattern.toString(exec);
+    int matchPos = source.find(patternString);
+    int matchLen = patternString.size();
+    // Do the replacement
+    if (matchPos == -1)
+      return String(source);
+    else {
+      return String(source.substr(0, matchPos) + replacement.toString(exec) + source.substr(matchPos + matchLen));
+    }
+  }
+}
+
 // ECMA 15.5.4.2 - 15.5.4.20
 Value StringProtoFuncImp::call(ExecState *exec, Object &thisObj, const List &args)
 {
@@ -321,70 +480,7 @@ Value StringProtoFuncImp::call(ExecState *exec, Object &thisObj, const List &arg
     break;
   }
   case Replace:
-    u = s;
-    if (a0.type() == ObjectType && a0.toObject(exec).inherits(&RegExpImp::info)) {
-      RegExpImp* imp = static_cast<RegExpImp *>( a0.toObject(exec).imp() );
-      RegExp *reg = imp->regExp();
-      bool global = false;
-      Value tmp = imp->get(exec,"global");
-      if (tmp.type() != UndefinedType && tmp.toBoolean(exec) == true)
-        global = true;
-
-      RegExpObjectImp* regExpObj = static_cast<RegExpObjectImp*>(exec->lexicalInterpreter()->builtinRegExp().imp());
-      int lastIndex = 0;
-      u3 = a1.toString(exec); // replacement string
-      // This is either a loop (if global is set) or a one-way (if not).
-      do {
-        int **ovector = regExpObj->registerRegexp( reg, u );
-        UString mstr = reg->match(u, lastIndex, &pos, ovector);
-        regExpObj->setSubPatterns(reg->subPatterns());
-        if (pos == -1)
-          break;
-        len = mstr.size();
-        UString rstr(u3);
-        bool ok;
-        // check if u3 matches $1 or $2 etc
-        for (int i = 0; (i = rstr.find(UString("$"), i)) != -1; i++) {
-          if (i+1<rstr.size() && rstr[i+1] == '$') {  // "$$" -> "$"
-            rstr = rstr.substr(0,i) + "$" + rstr.substr(i+2);
-            continue;
-          }
-          // Assume number part is one char exactly
-          unsigned long pos = rstr.substr(i+1,1).toULong(&ok, false /* tolerate empty string */);
-          if (ok && pos <= (unsigned)reg->subPatterns()) {
-            rstr = rstr.substr(0,i)
-                      + u.substr((*ovector)[2*pos],
-                                     (*ovector)[2*pos+1]-(*ovector)[2*pos])
-                      + rstr.substr(i+2);
-            i += (*ovector)[2*pos+1]-(*ovector)[2*pos] - 1; // -1 offsets i++
-          }
-        }
-        lastIndex = pos + rstr.size();
-        u = u.substr(0, pos) + rstr + u.substr(pos + len);
-        //fprintf(stderr,"pos=%d,len=%d,lastIndex=%d,u=%s\n",pos,len,lastIndex,u.ascii());
-
-        // special case of empty match
-        if (len == 0) {
-          lastIndex = lastIndex + 1;
-          if (lastIndex > u.size())
-            break;
-        }
-      } while (global);
-
-      result = String(u);
-    } else { // First arg is a string
-      u2 = a0.toString(exec);
-      pos = u.find(u2);
-      len = u2.size();
-      // Do the replacement
-      if (pos == -1)
-        result = String(s);
-      else {
-        u3 = u.substr(0, pos) + a1.toString(exec) +
-             u.substr(pos + len);
-        result = String(u3);
-      }
-    }
+    result = replace(exec, s, a0, a1);
     break;
   case Slice: // http://developer.netscape.com/docs/manuals/js/client/jsref/string.htm#1194366
     {
index d21af1d3b27923c4986cdc35cdab56b5db553f79..303621b973389a6af1ce5dcfd9b279d3dd9c5dc6 100644 (file)
@@ -606,6 +606,41 @@ UString UString::from(double d)
   return UString(buf);
 }
 
+UString UString::spliceSubstringsWithSeparators(const Range *substringRanges, int rangeCount, const UString *separators, int separatorCount) const
+{
+  int totalLength = 0;
+
+  for (int i = 0; i < rangeCount; i++) {
+    totalLength += substringRanges[i].length;
+  }
+  for (int i = 0; i < separatorCount; i++) {
+    totalLength += separators[i].size();
+  }
+
+  UChar *buffer = static_cast<UChar *>(malloc(totalLength * sizeof(UChar)));
+
+  int maxCount = MAX(rangeCount, separatorCount);
+  int bufferPos = 0;
+  for (int i = 0; i < maxCount; i++) {
+    if (i < rangeCount) {
+      memcpy(buffer + bufferPos, data() + substringRanges[i].position, substringRanges[i].length * sizeof(UChar));
+      bufferPos += substringRanges[i].length;
+    }
+    if (i < separatorCount) {
+      memcpy(buffer + bufferPos, separators[i].data(), separators[i].size() * sizeof(UChar));
+      bufferPos += separators[i].size();
+    }
+  }
+
+  UString::Rep *rep = UString::Rep::create(buffer, totalLength);
+  UString result = UString(rep);
+  rep->deref();
+
+  return result;
+}
+
+
+
 UString &UString::append(const UString &t)
 {
   int thisSize = size();
index 03e2ae23dcc81724e4a555d6c2ea744e1dcd2d18..34f5da917c28e0478521db901eb04d99eed0b367 100644 (file)
@@ -306,6 +306,16 @@ namespace KJS {
      */
     static UString from(double d);
 
+    struct Range {
+    public:
+      Range(int pos, int len) : position(pos), length(len) {}
+      Range() {}
+      int position;
+      int length;
+    };
+
+    UString spliceSubstringsWithSeparators(const Range *substringRanges, int rangeCount, const UString *separators, int separatorCount) const;
+
     /**
      * Append another string.
      */