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 9d56006..744a4f8 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 16d6877..7d4abe4 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 d21af1d..303621b 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 03e2ae2..34f5da9 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.
      */