Bug 820124, Part 2/2 - Handle fast removal in str_replace(). r=dvander
authorSean Stangl <sstangl@mozilla.com>
Tue, 18 Dec 2012 17:28:16 -0800
changeset 125952 f95b0378d4eeefbd6e61e1d3a02643cc990906e5
parent 125951 047534c2220799f6e74de47f0b23af1ee78df4ee
child 125953 c3b8f166c3b5d139e0ae165bd91f5bdf3ff53133
push id2151
push userlsblakk@mozilla.com
push dateTue, 19 Feb 2013 18:06:57 +0000
treeherdermozilla-beta@4952e88741ec [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdvander
bugs820124
milestone20.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 820124, Part 2/2 - Handle fast removal in str_replace(). r=dvander
js/src/jsstr.cpp
js/src/vm/RegExpObject.cpp
--- a/js/src/jsstr.cpp
+++ b/js/src/jsstr.cpp
@@ -2303,28 +2303,141 @@ BuildDollarReplacement(JSContext *cx, JS
            builder.append(newReplace) &&
            builder.append(rightSide));
 #undef ENSURE
 
     args->rval().setString(builder.result());
     return true;
 }
 
+struct StringRange
+{
+    size_t start;
+    size_t length;
+
+    StringRange(size_t s, size_t l)
+      : start(s), length(l)
+    { }
+};
+
+static JSString *
+AppendSubstrings(JSContext *cx, Handle<JSStableString*> stableStr,
+                 const StringRange *ranges, size_t rangesLen)
+{
+    JS_ASSERT(rangesLen);
+
+    /* For single substrings, construct a dependent string. */
+    if (rangesLen == 1)
+        return js_NewDependentString(cx, stableStr, ranges[0].start, ranges[0].length);
+
+    /* Collect substrings into a rope. */
+    RopeBuilder rope(cx);
+    for (size_t i = 0; i < rangesLen; i++) {
+        const StringRange &sr = ranges[i];
+
+        RootedString substr(cx, js_NewDependentString(cx, stableStr, sr.start, sr.length));
+        if (!substr)
+            return NULL;
+
+        /* Appending to the rope permanently roots the substring. */
+        rope.append(substr);
+    }
+
+    return rope.result();
+}
+
+static bool
+str_replace_regexp_remove(JSContext *cx, CallArgs args, HandleString str, RegExpShared &re)
+{
+    Rooted<JSStableString*> stableStr(cx, str->ensureStable(cx));
+    if (!stableStr)
+        return false;
+
+    Vector<StringRange, 16, SystemAllocPolicy> ranges;
+
+    StableCharPtr chars = stableStr->chars();
+    size_t charsLen = stableStr->length();
+
+    MatchPair match;
+    size_t lastIndex = 0;
+
+    /* Accumulate StringRanges for unmatched substrings. */
+    while (lastIndex <= charsLen) {
+        if (!JS_CHECK_OPERATION_LIMIT(cx))
+            return false;
+
+        size_t startIndex = lastIndex;
+
+        RegExpRunStatus status = re.executeMatchOnly(cx, chars, charsLen, &lastIndex, match);
+        if (status == RegExpRunStatus_Error)
+            return false;
+        if (status == RegExpRunStatus_Success_NotFound)
+            break;
+
+        /* Include the latest unmatched substring. */
+        if (size_t(match.start) > startIndex) {
+            if (!ranges.append(StringRange(startIndex, match.start - startIndex)))
+                return false;
+        }
+
+        if (match.isEmpty())
+            lastIndex++;
+
+        /* Non-global removal executes at most once. */
+        if (!re.global())
+            break;
+    }
+
+    /* If unmatched, return the input string. */
+    if (!lastIndex) {
+        args.rval().setString(str);
+        return true;
+    }
+
+    /* The last successful match updates the RegExpStatics. */
+    cx->regExpStatics()->updateLazily(cx, stableStr, &re, lastIndex);
+
+    /* Include any remaining part of the string. */
+    if (lastIndex < charsLen) {
+        if (!ranges.append(StringRange(lastIndex, charsLen - lastIndex)))
+            return false;
+    }
+
+    /* Handle the empty string before calling .begin(). */
+    if (ranges.empty()) {
+        args.rval().setString(cx->runtime->emptyString);
+        return true;
+    }
+
+    JSString *result = AppendSubstrings(cx, stableStr, ranges.begin(), ranges.length());
+    if (!result)
+        return false;
+
+    args.rval().setString(result);
+    return true;
+}
+
 static inline bool
 str_replace_regexp(JSContext *cx, CallArgs args, ReplaceData &rdata)
 {
     if (!rdata.g.normalizeRegExp(cx, true, 2, args))
         return false;
 
     rdata.leftIndex = 0;
     rdata.calledBack = false;
 
     RegExpStatics *res = cx->regExpStatics();
     RegExpShared &re = rdata.g.regExp();
 
+    /* Optimize removal. */
+    if (rdata.repstr && rdata.repstr->length() == 0 && !rdata.dollar) {
+        JS_ASSERT(!rdata.lambda && !rdata.elembase);
+        return str_replace_regexp_remove(cx, args, rdata.str, re);
+    }
+
     Value tmp;
     if (!DoMatch(cx, res, rdata.str, re, ReplaceRegExpCallback, &rdata, REPLACE_ARGS, &tmp))
         return false;
 
     if (!rdata.calledBack) {
         /* Didn't match, so the string is unmodified. */
         args.rval().setString(rdata.str);
         return true;
--- a/js/src/vm/RegExpObject.cpp
+++ b/js/src/vm/RegExpObject.cpp
@@ -117,18 +117,18 @@ MatchPairs::initArray(size_t pairCount)
     JS_ASSERT(pairCount > 0);
 
     /* Guarantee adequate space in buffer. */
     if (!allocOrExpandArray(pairCount))
         return false;
 
     /* Initialize all MatchPair objects to invalid locations. */
     for (size_t i = 0; i < pairCount; i++) {
-        pairs_[i].start = size_t(-1);
-        pairs_[i].limit = size_t(-1);
+        pairs_[i].start = -1;
+        pairs_[i].limit = -1;
     }
 
     return true;
 }
 
 bool
 MatchPairs::initArrayFrom(MatchPairs &copyFrom)
 {