Bug 820124, Part 2/2 - Handle fast removal in str_replace(). r=dvander
☠☠ backed out by c55e74c41184 ☠ ☠
authorSean Stangl <sstangl@mozilla.com>
Tue, 18 Dec 2012 17:28:16 -0800
changeset 126182 038194a2ffc38c3d893cfe8e8c81a987a149e29f
parent 126181 4a7071b920691e2ac545cb59a3fc074d4b904640
child 126183 a146aac182ef4a0f43474b37d3c88ffc1f587c51
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,142 @@ 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 startIndex = 0; /* Index used for iterating through the string. */
+    size_t lastIndex = 0;  /* Index after last successful match. */
+
+    /* Accumulate StringRanges for unmatched substrings. */
+    while (startIndex <= charsLen) {
+        if (!JS_CHECK_OPERATION_LIMIT(cx))
+            return false;
+
+        RegExpRunStatus status = re.executeMatchOnly(cx, chars, charsLen, &startIndex, match);
+        if (status == RegExpRunStatus_Error)
+            return false;
+        if (status == RegExpRunStatus_Success_NotFound)
+            break;
+
+        /* Include the latest unmatched substring. */
+        if (size_t(match.start) > lastIndex) {
+            if (!ranges.append(StringRange(lastIndex, match.start - lastIndex)))
+                return false;
+        }
+
+        lastIndex = startIndex;
+
+        /* Non-global removal executes at most once. */
+        if (!re.global())
+            break;
+
+        if (match.isEmpty())
+            lastIndex++;
+    }
+
+    /* 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)
 {