Changeset 59161 in webkit for trunk/JavaScriptCore/runtime/JSString.cpp

Timestamp:

May 11, 2010, 11:42:46 AM (15 years ago)

Author:

[email protected]

Message:

Start using ropes in String.prototype.replace.

Reviewed by Oliver Hunt and Darin Adler.

1%-1.5% speedup on SunSpider.

• runtime/JSString.cpp:

(JSC::JSString::resolveRope): Updated for RopeImpl refactoring.

(JSC::JSString::replaceCharacter): Added a replaceCharacter function, which creates
a rope for the resulting replacement.

• runtime/JSString.h: A few changes here:

(JSC::):
(JSC::RopeBuilder::RopeIterator::RopeIterator):
(JSC::RopeBuilder::RopeIterator::operator++):
(JSC::RopeBuilder::RopeIterator::operator*):
(JSC::RopeBuilder::RopeIterator::operator!=):
(JSC::RopeBuilder::RopeIterator::WorkItem::WorkItem):
(JSC::RopeBuilder::RopeIterator::WorkItem::operator!=):
(JSC::RopeBuilder::RopeIterator::skipRopes): Created a RopeIterator abstraction.
We use this to do a substring find without having to resolve the rope.
(We could use this iterator when resolving ropes, too, but resolving
ropes backwards is usually more efficient.)

(JSC::RopeBuilder::JSString): Added constructors for 2 & 3 UStrings.

(JSC::RopeBuilder::appendValueInConstructAndIncrementLength):
(JSC::RopeBuilder::size): Updated for RopeImpl refactoring.

• runtime/Operations.h: Updated for RopeImpl refactoring.

(JSC::jsString): Added jsString functions for 2 & 3 UStrings.

• runtime/RopeImpl.cpp:

(JSC::RopeImpl::derefFibersNonRecursive):

• runtime/RopeImpl.h:

(JSC::RopeImpl::initializeFiber):
(JSC::RopeImpl::size):
(JSC::RopeImpl::fibers):
(JSC::RopeImpl::deref):
(JSC::RopeImpl::RopeImpl): A little refactoring to make this patch easier:
Moved statics to the top of the class; put multi-statement functions on
multiple lines; renamed "fiberCount" to "size" to match other collections;
changed the "fibers" accessor to return the fibers buffer, instead of an
item in the buffer, to make iteration easier.

• runtime/StringPrototype.cpp:

(JSC::stringProtoFuncReplace): Don't resolve a rope unless we need to. Do
use our new replaceCharacter function if possible. Do use a rope to
represent splicing three strings together.

File:

• trunk/JavaScriptCore/runtime/JSString.cpp (modified) (2 diffs)

trunk/JavaScriptCore/runtime/JSString.cpp

@@ -76 +76 @@
             unsigned fiberCountMinusOne = rope->fiberCount() - 1;
             for (unsigned i = 0; i < fiberCountMinusOne; ++i)
-                workQueue.append(rope->fibers(i));
-            currentFiber = rope->fibers(fiberCountMinusOne);
+                workQueue.append(rope->fibers()[i]);
+            currentFiber = rope->fibers()[fiberCountMinusOne];
         } else {
             UStringImpl* string = static_cast<UStringImpl*>(currentFiber);
@@ -105 +105 @@
 }
 
+JSValue JSString::replaceCharacter(ExecState* exec, UChar character, const UString& replacement)
+{
+    if (!isRope()) {
+        size_t matchPosition = m_value.find(character);
+        if (matchPosition == notFound)
+            return JSValue(this);
+        return jsString(exec, m_value.substr(0, matchPosition), replacement, m_value.substr(matchPosition + 1));
+    }
+
+    RopeIterator end;
+    
+    // Count total fibers and find matching string.
+    size_t fiberCount = 0;
+    UStringImpl* matchString = 0;
+    size_t matchPosition = notFound;
+    for (RopeIterator it(m_other.m_fibers, m_fiberCount); it != end; ++it) {
+        ++fiberCount;
+        if (matchString)
+            continue;
+
+        UStringImpl* string = *it;
+        matchPosition = string->find(character);
+        if (matchPosition == notFound)
+            continue;
+        matchString = string;
+    }
+
+    if (!matchString)
+        return this;
+
+    RopeBuilder builder(replacement.size() ? fiberCount + 2 : fiberCount + 1);
+    if (UNLIKELY(builder.isOutOfMemory()))
+        return throwOutOfMemoryError(exec);
+
+    for (RopeIterator it(m_other.m_fibers, m_fiberCount); it != end; ++it) {
+        UStringImpl* string = *it;
+        if (string != matchString) {
+            builder.append(UString(string));
+            continue;
+        }
+
+        builder.append(UString(string).substr(0, matchPosition));
+        if (replacement.size())
+            builder.append(replacement);
+        builder.append(UString(string).substr(matchPosition + 1));
+    }
+
+    JSGlobalData* globalData = &exec->globalData();
+    return JSValue(new (globalData) JSString(globalData, builder.release()));
+}
+
 JSString* JSString::getIndexSlowCase(ExecState* exec, unsigned i)
 {