614608 - String.prototype.split argument evaluation order is wrong

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

Maybe a bit lame, but ES5 requires String.prototype.split to call ToUInt32(limit) before calling ToString(separator) (step 2 and step 8).

Test case (should print 'ab' instead of 'ba'):
---
var order = '';
var o1 = { toString: function() { order += 'b'; return ''; }};
var o2 = { valueOf:  function() { order += 'a'; return 2; }};
'xyz'.split(o1, o2);
print(order);
---
This is responsible for 2 sputnik failures.

Comment 1

[Jan de Mooij [:jandem]]

(In reply to comment #0)
> (step 2 and step 8).

Step 5 instead of step 2.

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Patch

Fix + test.

Comment 3

[Jeff Walden [:Waldo]]

Comment on attachment 493053 [details] [diff] [review]
Patch

Wow, this really is lame.  :-)  I'd thought the algorithms made a point of construing arguments left-to-right when conversions might be necessary (and had even broken compatibility in one place to do this), but that's clearly either not the case or this instance was an oversight.

Since you're here, and since this ordering of conversions is unusual and seems likely to be perceived as buggy absent comments hinting otherwise, could you mark up str_split with step-by-step comments like js_fun_apply is marked up?  That is, add /* ES5 15.5.4.14 */ before the function definition, and at the relevant places add /* Step N. */ or /* Steps M-N. */ or /* Steps J,K,M-N */ or whatever's necessary to point out when each step occurs.  If you can't map precisely for any steps for whatever reason, just do whatever's reasonable -- the idea's just to make clear when steps happen (and also to imply that the algorithm has been deliberately implemented to coincide with the spec, rather than merely implementing something mostly but not entirely like the spec).  Thanks in advance!

Comment 4

[Jan de Mooij [:jandem]]

Attachment: Patch v2

This also fixes the s.split(undefined) case which is mentioned explicitly (and every other engine fails) It might make the code slightly more complex (though the algorithm looks more like the steps in ES5); not sure whether this is worth it.

Comment 5

[Jeff Walden [:Waldo]]

Sheesh, this algorithm is complicated with optimizations.  (Although, to be fair, the spec steps are a bit strange too.)  It's very tempting to finish up the review now, but the more I look the clearer it becomes that it's going to be hard and time-consuming to do this justice.  I'll swing back to this once our blocker numbers are down in well-managed spitting distance of zero, and then (probably) we can get it in the JM branch until TM isn't gated on back-merges.

Comment 6

[Jeff Walden [:Waldo]]

Going through this now, should have full review comments in the next couple hours, or tomorrow at worst, just wanted to note preliminarily that the patch is bitrotted slightly.  Instead of NORMALIZE_THIS there's now this:

    JSString *str = ThisToStringForStringProto(cx, vp);
    if (!str)
        return false;

So at a minimum the patch needs to be refreshed (seems trivially) to account for that.

Comment 7

[Jeff Walden [:Waldo]]

Comment on attachment 493297 [details] [diff] [review]
Patch v2

>diff --git a/js/src/jsstr.cpp b/js/src/jsstr.cpp

>+    /* Step 5: Use the second argument as the split limit, if given. */
>+    uint32 limit;
>+    if (argc > 1 && !vp[3].isUndefined()) {
>+        jsdouble d;
>+        if (!ValueToNumber(cx, vp[3], &d))
>+            return false;
>+
>+        /* Clamp limit between 0 and 1 + string length. */
>+        limit = js_DoubleToECMAUint32(d);
>+        if (limit > str->length())
>+            limit = 1 + str->length();
>+    } else {
>+        limit = uint32(-1);

UINT32_MAX

>+    }
>+
>+    /* Step 8. */
>+    RegExp *re = NULL; /* avoid warnings */
>+    JSSubString *sep = NULL, tmp = js_EmptySubString;
>+    bool sepUndefined = (argc == 0 || vp[2].isUndefined());
>+    if (!sepUndefined) {
>+        if (VALUE_IS_REGEXP(cx, vp[2])) {
>+            re = static_cast<RegExp *>(vp[2].toObject().getPrivate());
>+            sep = &tmp;
>+
>+            /* Set a magic value so we can detect a successful re match. */
>+            sep->chars = NULL;
>+            sep->length = 0;
>+        } else {
>+            JSString *str2 = js_ValueToString(cx, vp[2]);
>+            if (!str2)
>+                return false;
>+            vp[2].setString(str2);
>+
>+            /*
>+             * Point sep at a local copy of str2's header because find_split
>+             * will modify sep->length.
>+             */
>+            str2->getCharsAndLength(tmp.chars, tmp.length);
>+            sep = &tmp;
>+            re = NULL;

This needs updating for the linear/flat/normal string stuff and getChars() fallibility, and potentially for JSSubString changes if any happened (I'm betting with no evidence there were some).


>+        }
>+    }
>+    /* Step 9. */
>+    if (limit == 0) {
>+        JSObject *aobj = js_NewArrayObject(cx, 0, NULL);
>+        if (!aobj)
>+            return false;
>+        vp->setObject(*aobj);
>+        return true;
>+    }
>+    /* Step 10. */
>+    if (sepUndefined) {
>         Value v = StringValue(str);
>         JSObject *aobj = js_NewArrayObject(cx, 1, &v);
>         if (!aobj)
>             return false;
>         vp->setObject(*aobj);
>         return true;
>     }

This bit looks like it needs updating for array-creation method renaming/refactoring.


>-
>-    RegExp *re;
>-    JSSubString *sep, tmp;
>-    if (VALUE_IS_REGEXP(cx, vp[2])) {
>-        re = static_cast<RegExp *>(vp[2].toObject().getPrivate());
>-        sep = &tmp;
>-
>-        /* Set a magic value so we can detect a successful re match. */
>-        sep->chars = NULL;
>-        sep->length = 0;
>-    } else {
>-        JSString *str2 = js_ValueToString(cx, vp[2]);
>-        if (!str2)
>-            return false;
>-        vp[2].setString(str2);
>-
>-        /*
>-         * Point sep at a local copy of str2's header because find_split
>-         * will modify sep->length.
>-         */
>-        str2->getCharsAndLength(tmp.chars, tmp.length);
>-        sep = &tmp;
>-        re = NULL;
>-    }
>-
>-    /* Use the second argument as the split limit, if given. */
>-    uint32 limit = 0; /* Avoid warning. */
>-    bool limited = (argc > 1) && !vp[3].isUndefined();
>-    if (limited) {
>-        jsdouble d;
>-        if (!ValueToNumber(cx, vp[3], &d))
>-            return false;
>-
>-        /* Clamp limit between 0 and 1 + string length. */
>-        limit = js_DoubleToECMAUint32(d);
>-        if (limit > str->length())
>-            limit = 1 + str->length();
>-    }
>-
>+    /* Steps 4, 6-7, 11-14. */
>     AutoValueVector splits(cx);
> 
>     RegExpStatics *res = cx->regExpStatics();
>     jsint i, j;
>     uint32 len = i = 0;
>     while ((j = find_split(cx, res, str, re, &i, sep)) >= 0) {
>-        if (limited && len >= limit)
>+        if (len >= limit)
>             break;
> 
>         JSString *sub = js_NewDependentString(cx, str, i, size_t(j - i));
>         if (!sub || !splits.append(StringValue(sub)))
>             return false;
>         len++;
> 
>         /*
>          * Imitate perl's feature of including parenthesized substrings that
>          * matched part of the delimiter in the new array, after the split
>          * substring that was delimited.
>          */
>         if (re && sep->chars) {
>             for (uintN num = 0; num < res->getParenCount(); num++) {
>-                if (limited && len >= limit)
>+                if (len >= limit)
>                     break;
>                 JSSubString parsub;
>                 res->getParen(num, &parsub);
>                 sub = js_NewStringCopyN(cx, parsub.chars, parsub.length);
>                 if (!sub || !splits.append(StringValue(sub)))
>                     return false;
>                 len++;
>             }
>             sep->chars = NULL;
>         }
>         i = j + sep->length;
>     }
> 
>     if (j == -2)
>         return false;
> 
>+    /* Steps 3, 15. */
>     JSObject *aobj = js_NewArrayObject(cx, splits.length(), splits.begin());
>     if (!aobj)
>         return false;
>+
>+    /* Step 16. */
>     vp->setObject(*aobj);
>     return true;
> }
> 
> #if JS_HAS_PERL_SUBSTR
> static JSBool
> str_substr(JSContext *cx, uintN argc, Value *vp)
> {


Tests look good (and mind-blowing, I must say!).

Even with the stepwise comments, I can't follow our implementation compared to the spec algorithms.  It looks plausibly correct, but when I hit the find_split non-spec algorithm I lose any ability to determine whether our algorithm and the spec algorithm are identical.  Would it be worthwhile going further down the look-like-the-spec road here?  In particular step 13 in the spec looks nothing like what we have in the code, and we entangle it with step 11 as well.  And find_split looks only about a quarter of the way like SplitMatch, or that plus sub-steps in step 13.  What if we actually implemented a SplitMatch helper, rather than our own thing here?  (Another interesting idea: what if we moved steps 11-13 into a templatized helper function, then instantiated different versions of it for the case where R is a regular expression, and for the case where R is a string, say by passing in a class with an operator(string, index, separator) that the templated method would call?  We'd get better readability and improved performance both.)  If you don't have time to do this, let me know and I'll take it -- but given the complexity of the current code, it seems better for the web (even if it's only in nightlies) to do it all at once than to have a not-easily-scrutinized halfway step.

Comment 8

[Jan de Mooij [:jandem]]

(In reply to comment #7)
> Comment on attachment 493297 [details] [diff] [review]

That sounds awesome. Rewriting it to read more like the spec may also prevent further surprises in the future. I can fix this month but feel free to steal if you need it sooner or want to do this yourself.

Comment 9

[Jan de Mooij [:jandem]]

Attachment: Patch v3

Rewrites split to be more like the spec. Passes jstests and jit-tests. Still need to add comments, rename some variables and run more tests.

Comment 10

[Jan de Mooij [:jandem]]

Attachment: Patch

Remove more code, fix tests in bug 611181, add comments, fix error-handling. Next week I will post a patch for review.

Comment 11

[Tom S. (please needinfo tschuster)]

I think your code could use ValueToIntegerRange in step 5.

Comment 12

[Jan de Mooij [:jandem]]

Attachment: Patch

Waldo, I hope this is what you had in mind. 

Please turn on your -pedantic flag when reviewing this. For instance, when would you use "unsigned", "uint32", "jsuint" or "uintN"?

Tom: thanks for the suggestion but I need the value as uint32, so I think it's clearer this way. Let me know if I'm missing something.

Comment 13

[Jan de Mooij [:jandem]]

Btw, perf is not much affected, maybe 1-2% faster. I suppose because we don't have to check for regexp or captures in the separator-is-string case.

Comment 14

[Jeff Walden [:Waldo]]

Comment on attachment 517462 [details] [diff] [review]
Patch

This is all excellent, pretty much exactly what I was looking for.  With this patch the split code is much more readable and straightforwardly spec-compliant than what we had before.  I'm not entirely surprised it's only a percent or two better perf-wise, but those increments add up.  Some comments, a couple reasonably substantive but not particularly difficult to address, and this should be golden.

Also, for what it's worth, this is probably the most complex ~20K patch I've ever had to review.  So many edge cases to consider, optimizations to account for, etc.  I'm doubly glad I didn't try to review this, or request these changes, when you first submitted the patch a couple months ago.  :-)


>diff --git a/js/src/jsstr.cpp b/js/src/jsstr.cpp

>+struct SplitMatchResult {
>+private:
>+    unsigned endIndex;
>+    unsigned length;
>+public:

These should be size_t, not unsigned.

Half-indent public/private by two spaces.  Also, since you have private members, I'd make this a class (and with that you can get rid of the private specifier, which our classes that start with private data members have been doing lately).


>+    void setFailure() {
>+        endIndex = INT32_MAX;
>+    }

Move the isFailure definition up next to this, for slightly better readability.


>+    unsigned getEndIndex() const {
>+        JS_ASSERT(!isFailure());
>+        return endIndex;
>+    }
>+    unsigned getLength() const {
>+        JS_ASSERT(!isFailure());
>+        return length;
>+    }

In our naming convention a "get" prefix often indicates fallibility, so make this endIndex(), likewise length() rather than getLength().


>+    void setResult(unsigned length, unsigned endIndex) {
>+        this->length = length;
>+        this->endIndex = endIndex;
>+    }
>+    bool isFailure() const {
>+        return (endIndex == INT32_MAX);
>+    }

Since these values should be sizes, SIZE_MAX seems a slightly better sentinel.  Also add a JS_STATIC_ASSERT(SIZE_MAX > JSString::MAX_LENGTH), just to be absolutely sure there is no, and will never be, a collision.


>+template<class Matcher>
>+static JSObject *SplitHelper(JSContext *cx, JSLinearString *str, JSSubString *sep, uint32 limit, Matcher match) {

Wrap the lines this way, please:

template<class Matcher>
static JSObject *
SplitHelper(JSContext *cx, JSLinearString *str, JSSubString *sep, uint32 limit, Matcher match)
{

|sep| isn't necessary.  If the matcher is a regular expression it's very nearly ignored -- you can just make a JSSubString in SplitRegExpMatcher::operator() to get the last match, and plausibly the compiler could even optimize the JSSubString out.  If the matcher is a string, you can pass the separator as a parameter to the matcher itself.


>+    unsigned strlen = str->length();

size_t


>+    SplitMatchResult result;
>+
>+    /* Step 11. */
>+    if (strlen == 0) {
>+        if (!match(cx, str, 0, sep, &result))
>+            return NULL;

It seems very slightly better to me to name this splitMatch, but feel free to leave this if you think it's better this way.


>+        if (!result.isFailure()) {
>+            return NewDenseCopiedArray(cx, 0, NULL);
>+        } else {
>+            Value v = StringValue(str);
>+            return NewDenseCopiedArray(cx, 1, &v);
>+        }

There's no need for an else here: the if-body always returns.  So de-indent the body of the else, remove the else and braces, and add a blank line between the two.

With that the if is a single line, so no need for braces.

Also, the if should be NewDenseEmptyArray.


>+    /* Step 12. */
>+    unsigned lastEndIndex = 0;
>+    unsigned index = 0;

More size_t.


>+    /* Step 13. */
>+    AutoValueVector splits(cx);
>+
>+    while (index < strlen) {
>+        /* Step 13a. */
>+        if (!match(cx, str, index, sep, &result))
>+            return NULL;
>+
>+        /* 
>+         * Step 13b. Note: our optimized StringMatch looks for sep until the 
>+         * end of the string so we can break out of the loop here.
>+         */
>+        if (result.isFailure())
>+            break;

Excellent comment, going through the patch in-order this would have confused me but for it.  (Although I suggest changes to it later in this comment.)


>+        /* Step 13c. */

This is a pretty big step, so it seems to me it could use more than just this one comment.  (I have no idea what canonical/proper style is for noting, say, 13(c)(iii)(7)c. -- do something reasonable to the extent there is any such thing.  :-) )  Certainly at least 13(c)(iii)(7) depth seems warranted.


>+        if (endIndex == lastEndIndex) {
>+            index++;
>+            continue;
>+        }
>+        size_t sublength = size_t(endIndex - result.getLength() - lastEndIndex);

Add some assertions to verify that the subtractions here don't underflow.


>+        JSString *sub = js_NewDependentString(cx, str, lastEndIndex, sublength);
>+        if (!sub || !splits.append(StringValue(sub)))
>+            return NULL;
>+        
>+        if (splits.length() == limit)
>+            return NewDenseCopiedArray(cx, splits.length(), splits.begin());
>+        
>+        lastEndIndex = endIndex;
>+        
>+        // Compiler can remove this "if" for the common non-RegExp case.
>+        if (Matcher::returnsCaptures()) {

I'd remove the comment.  It's a pretty core feature of templates that they'll do this, so it doesn't need to be specifically called out.  Although, you probably should just make returnsCaptures a static boolean member -- no need for an inline function that semi-plausibly the compiler might not inline, and (perhaps more importantly) which debuggers might needlessly step into and out of during debugging.


>+            RegExpStatics *res = cx->regExpStatics();
>+            for (unsigned i = 0; i < res->parenCount(); i++) {
>+                if (res->pairIsPresent(i + 1)) {
>+                    JSSubString parsub;
>+                    res->getParen(i + 1, &parsub);
>+                    sub = js_NewStringCopyN(cx, parsub.chars, parsub.length);
>+                    if (!sub || !splits.append(StringValue(sub)))
>+                        return NULL;
>+                } else {
>+                    if (!splits.append(UndefinedValue()))
>+                        return NULL;
>+                }

This change looks like it's per-spec, but it also looks like implementations don't behave this way: if the pair's not present IE9, Opera, Nitro, V8, and old-us all use "" rather than |undefined|.  So this seems a spec bug.  Could you change the else-branch to append StringValue(cx->runtime->emptyString) instead, and if you have time report the problem to es-discuss (or tell me and I will)?  Also add a comment saying this is a spec deviation (that's very likely a spec bug), and feel free to include a link to the es-discuss thread if you start one.  No worries if you don't, I'm perfectly willing to do it too.


>+                if (splits.length() == limit)
>+                    break;
>+            }

The limit-break breaks out of the capturing loop, but really it should return out of the entire spec algorithm.  This seems to change behavior on this testcase:

js> "abc".split(/((()))./, 2) // with the changes
["", "", "", "", "", "", "", "", "", "", ""]

js> "abc".split(/((()))./, 2) // without the changes
["",""]

It seems the old code had the same limit-break bug, but -- somehow -- find_split didn't go awry when called again, I think because sep->chars got set to NULL.  (I refuse to debug the old algorithm and determine exactly why.  ;-) )  So just return a NewDenseCopiedArray instead of breaking here.  And add a test for this, since it seems we must not have one.


>+struct SplitRegExpMatcher {
>+private:
>+    RegExpStatics *res;
>+    RegExp *re;
>+public:
>+    SplitRegExpMatcher(RegExp *re, RegExpStatics *res) : res(res), re(re) {
>+    }
>+    inline static bool returnsCaptures() {

Again half-indent public/private, and change this to a class so you can remove private.


>-                 * If there was a trivial zero-length match at the end of the
>-                 * split, then we shouldn't output the matched string at the end
>-                 * of the split array. See ECMA-262 Ed. 3, 15.5.4.14, Step 15.
>-                 */
>-                sep->chars = NULL;
>-            }
>-        }
>-        JS_ASSERT((size_t)i >= sep->length);
>-        return i - sep->length;
>+        

Tab alert!  Please substitute in the appropriate number of spaces for tabs throughout the patch (I see other such uses).  And this seems as good a place as any to ask you to go through the patch and remove trailing whitespace.  If you don't have it enabled, the colordiff hg extension is invaluable (pipe through less -R) for pointing this out, and for viewing patches in general.


>+        /*
>+         * If there was a trivial zero-length match at the end of the
>+         * split, then we shouldn't output the matched string at the end
>+         * of the split array. For example, "abc".split(/\b/) -> ["abc"]
>+         *
>+         * However, if str is empty the result only depends on whether the regexp 
>+         * matches or not (ES5 15.5.4.14 step 11). In this case we don't 
>+         * want to fail here, e.g. "".split(/.?/) must return [].
>+         */
>+        if (sep->length == 0 && newIndex == str->length() && str->length() > 0)
>+            result->setFailure();
>+        else
>+            result->setResult(sep->length, newIndex);
>+        return true;
>     }

This bit confused me for a long time: it's necessary for the two examples to work, and the reason is that our match algorithm returns the next match wherever it is, including, or after, the specified index.  However, it seems to me it would be better and clearer if, rather than hacking these edge-cases here, we made the operation of the matchers consistently simple, added an explanatory comment saying how our SplitMatches differ from the spec SplitMatch (really, we should have a major comment above both Split*Matcher classes that explains what they do [and how they differ from SplitMatch in the spec]), and pushed this complexity to the calling locations (especially as only the non-empty string case needs it).  This diff demonstrates the changes I suggest (please make sure all three examples are in our existing tests while you're at it) -- they don't seem to break any tests, or the examples in the comments, as far as I can see:

######## BEGIN DIFF #########
diff --git a/js/src/jsstr.cpp b/js/src/jsstr.cpp
--- a/js/src/jsstr.cpp
+++ b/js/src/jsstr.cpp
@@ -2574,10 +2574,19 @@ static JSObject *SplitHelper(JSContext *
             return NULL;
 
-        if (!result.isFailure()) {
+        /*
+         * NB: Unlike in the non-empty string case, it's perfectly fine
+         *     (indeed the spec requires it) if we match at the end of the
+         *     string.  Thus these cases should hold:
+         *
+         *   var a = "".split("");
+         *   assertEq(a.length, 0);
+         *   var b = "".split(/.?/);
+         *   assertEq(b.length, 0);
+         */
+        if (!result.isFailure())
             return NewDenseCopiedArray(cx, 0, NULL);
-        } else {
-            Value v = StringValue(str);
-            return NewDenseCopiedArray(cx, 1, &v);
-        }
+
+        Value v = StringValue(str);
+        return NewDenseCopiedArray(cx, 1, &v);
     }
     
@@ -2594,18 +2603,32 @@ static JSObject *SplitHelper(JSContext *
             return NULL;
 
-        /* 
-         * Step 13b. Note: our optimized StringMatch looks for sep until the 
-         * end of the string so we can break out of the loop here.
+        /*
+         * Our match algorithm differs from the spec in that it returns the
+         * next index at which a match happens.  If no match happens we're
+         * done.
+         *
+         * But what if the match is at the end of the string (and the string is
+         * not empty)?  Per 13c(ii) this shouldn't be a match, so we have to
+         * specially exclude it.  Thus this case should hold:
+         *
+         *   var a = "abc".split(/\b/);
+         *   assertEq(a.length, 1);
+         *   assertEq(a[0], "abc");
          */
         if (result.isFailure())
             break;
-        
+
+        unsigned resultLen = result.getLength();
+        unsigned endIndex = result.getEndIndex();
+        if (resultLen == 0 && endIndex == str->length())
+            break;
+
         /* Step 13c. */
-        unsigned endIndex = result.getEndIndex();
         if (endIndex == lastEndIndex) {
             index++;
             continue;
         }
-        size_t sublength = size_t(endIndex - result.getLength() - lastEndIndex);
+
+        size_t sublength = size_t(endIndex - resultLen - lastEndIndex);
         JSString *sub = js_NewDependentString(cx, str, lastEndIndex, sublength);
         if (!sub || !splits.append(StringValue(sub)))
@@ -2669,17 +2692,5 @@ public:
         res->getLastMatch(sep);
         
-        /*
-         * If there was a trivial zero-length match at the end of the
-         * split, then we shouldn't output the matched string at the end
-         * of the split array. For example, "abc".split(/\b/) -> ["abc"]
-         *
-         * However, if str is empty the result only depends on whether the regexp 
-         * matches or not (ES5 15.5.4.14 step 11). In this case we don't 
-         * want to fail here, e.g. "".split(/.?/) must return [].
-         */
-        if (sep->length == 0 && newIndex == str->length() && str->length() > 0)
-            result->setFailure();
-        else
-            result->setResult(sep->length, newIndex);
+        result->setResult(sep->length, newIndex);
         return true;
     }
######### END DIFF ##########

>+struct SplitStringMatcher {
>+    inline static bool returnsCaptures() {
>+        return false;
>+    }
>+    inline bool operator()(JSContext *cx, JSLinearString *str, unsigned index, 
>+                           JSSubString *sep, SplitMatchResult *res) {
>+        const jschar *chars = str->chars();
>+        jsint match = StringMatch(chars + index, str->length() - index, sep->chars, sep->length);

Add some sanity bounds-checking assertions here, please, to make sure the matching doesn't read past the end of the string, while you're here.  You can never have too many bounds assertions.  :-)


>+    /* Step 5: Use the second argument as the split limit, if given. */
>+    uint32 limit;
>+    if (argc > 1 && !vp[3].isUndefined()) {
>+        jsdouble d;
>+        if (!ValueToNumber(cx, vp[3], &d))
>+            return false;
>+
>+        /* Clamp limit between 0 and 1 + string length. */
>+        limit = js_DoubleToECMAUint32(d);
>+        if (limit > str->length())
>+            limit = 1 + str->length();

Initially I thought this was an optimization, but it looks like it's not, and there's near-universal (save for us and Opera, and we don't agree with Opera) agreement on the spec algorithm:

js> "abc".split(/((((()))))./, 9) // what we do
["","","",""]

js> "abc".split(/((((()))))./, 9) // what the spec says/everyone else does
["","","","","","","","",""]

So it looks like you should get rid of the if-greater-than bit.  And can you add a test for this while you're at it?


>+    /* Step 8. */
>+    RegExp *re = NULL; /* avoid warnings */

With the algorithm refactoring here, this assignment seems necessary for correctness -- so the comment should go.


>+    JSSubString sep = js_EmptySubString;
>+    bool sepUndefined = (argc == 0 || vp[2].isUndefined());
>+    if (!sepUndefined) {
>+        if (VALUE_IS_REGEXP(cx, vp[2])) {
>+            re = static_cast<RegExp *>(vp[2].toObject().getPrivate());

*sadfaces that we don't have a getRegExpPrivate or something* (but you definitely shouldn't add that in this patch, it's complex enough already without that extraneous addition)


>+        } else {
>+            JSString *sepstr = js_ValueToString(cx, vp[2]);
>+            if (!sepstr)
>+                return false;
>+            vp[2].setString(sepstr);
>+
>+            sep.length = sepstr->length();
>+            sep.chars = sepstr->getChars(cx);

I suggest ensureLinear here.  And I'd say it's better to not have the sep substring thing here -- pass sepstr->assertIsLinear() directly to the SplitStringMatcher and have it extract out the chars and length and save them away.  (Comment by that that the string is anchored through its storage in vp[2] here.)


>+    /* Step 9. */
>+    if (limit == 0) {
>+        JSObject *aobj = NewDenseCopiedArray(cx, 0, NULL);
>+        if (!aobj)
>+            return false;

NewDenseEmptyArray again, please.


>+    /* Step 11-15. */

"Steps"

>+    JSObject *aobj;
>+    if (re)
>+        aobj = SplitHelper<SplitRegExpMatcher>(cx, strlin, &sep, limit, 
>+                   SplitRegExpMatcher(re, cx->regExpStatics()));
>+    else
>+        aobj = SplitHelper<SplitStringMatcher>(cx, strlin, &sep, limit, 
>+                   SplitStringMatcher());

If the consequence or alternative of an if (or the condition of the if) extends across multiple lines, consequence (and alternative if present) should be braced, so put some braces around the assignments here.

You're repeating yourself by explicitly parameterizing here, but Luke and I think that's not actually necessary, because the trail argument will constrain which templatized version can be chosen down to just one -- so kill the <..> bits here and cut down on wordiness.  :-)

Comment 15

[Jeff Walden [:Waldo]]

Hm, so I think I might have been wrong when I said browsers agreed on not putting |undefined| into split-arrays: now when I test other browsers using '.'.split(/(.)?(.)?/) I get them all putting |undefined| in the array, except for us.  So ignore where I say to change the paren-capturing loop to append the empty string rather than |undefined|.

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #15)
> Hm, so I think I might have been wrong when I said browsers agreed on not
> putting |undefined| into split-arrays: now when I test other browsers using
> '.'.split(/(.)?(.)?/) I get them all putting |undefined| in the array, except
> for us.  So ignore where I say to change the paren-capturing loop to append the
> empty string rather than |undefined|.

We have pre-ES3 split behavior, good to get it fixed finally. In fact find_split and all that dates from well before any ES spec for split or regexps.

Great patch and review!

/be

Comment 17

[Jan de Mooij [:jandem]]

Attachment: Patch v3

Fixed all review comments and added tests. I should have found some of these problems before submitting the patch, sorry for that. Anyway, I think this version is much better. Btw, the hg color extension is awesome :)

Comment 18

[Jan de Mooij [:jandem]]

Btw I adopted your 13(c)(iii)(7)(d) style. I also tried using a dot as seperator but didn't like it because there's also a dot at the end: 

Step 13.c.iii.7.d. 

If you think the parentheses are a bit too dense I'll happily change them to dots or something similar.

Comment 19

[Jan de Mooij [:jandem]]

Attachment: Patch v3b

Bed time, I guess, when I make spelling mistakes and don't notice them when reviewing the patch myself.

Comment 20

[Brendan Eich [:brendan]]

(In reply to comment #18)
> Btw I adopted your 13(c)(iii)(7)(d) style.

That's the preferred style. It is already in use, e.g., in jsxml.cpp.

/be

Comment 21

[Jan de Mooij [:jandem]]

Attachment: Patch v4

Steven Levithan will release the tests under the MIT license (awesome, thanks again!). I think we can include them now (there is more MIT-licensed code in the sunspider and v8 tests).

Comment 22

[Jan de Mooij [:jandem]]

Attachment: Patch v4

Forgot to qref a white space fix. Sorry for the noise.

Comment 23

[Jeff Walden [:Waldo]]

Comment on attachment 518022 [details] [diff] [review]
Patch v4

>diff --git a/js/src/jsstr.cpp b/js/src/jsstr.cpp

>+class SplitMatchResult {
>+    size_t endIndex_;
>+    size_t length_;
>+  public:
>+    void setFailure() {
>+        JS_STATIC_ASSERT(SIZE_MAX > JSString::MAX_LENGTH);
>+        endIndex_ = SIZE_MAX;
>+    }
>+    bool isFailure() const {
>+        return (endIndex_ == SIZE_MAX);
>+    }
>+    size_t endIndex() const {
>+        JS_ASSERT(!isFailure());
>+        return endIndex_;
>+    }
>+    size_t length() const {
>+        JS_ASSERT(!isFailure());
>+        return length_;
>+    }
>+    void setResult(size_t length, size_t endIndex) {
>+        length_ = length;
>+        endIndex_ = endIndex;
>+    }
>+};

We're usually more generous with blank lines -- one before 'public' at least.

>+template<class Matcher>
>+static JSObject *
>+SplitHelper(JSContext *cx, JSLinearString *str, uint32 limit,
>+            Matcher splitMatch)
> {

Wasn't thinking, but of course Bugzilla would have rewrapped what I typed out.  :-\  But it won't wrap > lines in attachment comments, so this is what I meant to say:

>template<class Matcher>
>static JSObject *
>SplitHelper(JSContext *cx, JSLinearString *str, uint32 limit, Matcher splitMatch)
>{

The Matcher bit only comes to 94 characters, and in SpiderMonkey code the character limit per line is 99 characters (it's 80 in the rest of Mozilla), and this is only 81 unless I mistyped something getting the length of that.


>+        if (sepLength == 0 && endIndex == str->length())
>+            break;

Seems like you already have strLength from earlier to use, rather than possibly re-getting the string length.


>+        /* Step 13(c)(iii). */
>+        JS_ASSERT(lastEndIndex < endIndex);
>+        JS_ASSERT(sepLength <= str->length());

Here too.


>+        /* Step 13(c)(iii)(6-7). */
>+        if (Matcher::returnsCaptures) {
>+            RegExpStatics *res = cx->regExpStatics();
>+            for (size_t i = 0; i < res->parenCount(); i++) {
>+                /* Steps 13(c)(iii)(7)(a-c). */
>+                if (res->pairIsPresent(i + 1)) {
>+                    JSSubString parsub;
>+                    res->getParen(i + 1, &parsub);
>+                    sub = js_NewStringCopyN(cx, parsub.chars, parsub.length);
>+                    if (!sub || !splits.append(StringValue(sub)))
>+                        return NULL;
>+                } else {
>+                    if (!splits.append(UndefinedValue()))
>+                        return NULL;
>+                }
>+                /* Step 13(c)(iii)(7)(d). */
>+                if (splits.length() == limit)
>+                    return NewDenseCopiedArray(cx, splits.length(), splits.begin());
>             }

We'd put a blank line after the if-else here to separate the exit from the append-the-capture bit.


>+    /* Steps 14-15. */
>+    JSString *sub = js_NewDependentString(cx, str, lastEndIndex,
>+                                          size_t(strLength - lastEndIndex));

I think this fits in exactly 99 characters if you don't wrap it.  Also, now that everything's size_t is there any need for the cast?  That would bring it well within 99 characters if not wrapped.


>+/*
>+ * The SplitMatch operation from ES5 15.5.4.14 is implemented using different
>+ * matchers for regular expression and string separators.
>+ *
>+ * The algorithm differs from the spec in that the matchers return the next
>+ * index at which a match happens.
>+ */

Might perhaps want to call this out as an optimization, but that's reasonably apparent if you think about it, and I think it's mentioned elsewhere, so this works well enough.


>+class SplitRegExpMatcher {
>+    RegExpStatics *res;
>+    RegExp *re;
>+  public:

Empty line before public.

>+    static const bool returnsCaptures = true;
>+    SplitRegExpMatcher(RegExp *re, RegExpStatics *res) : res(res), re(re) {
>+    }
>+    inline bool operator()(JSContext *cx, JSLinearString *str, size_t index,
>+                           SplitMatchResult *result) {

I'd also put one before the operator() method, since the stuff before it is setup-y and the operator is the core of the matcher.

>+        Value rval;
>+        size_t newIndex = size_t(index);

Without unsigneds, I think you can just use |index| instead of |newIndex| throughout this and get rid of the extra local variable completely.

>+        if (!re->execute(cx, res, str, &newIndex, true, &rval))
>+            return false;
>+        if (!rval.isTrue()) {
>+            result->setFailure();
>+            return true;
>+        }
>+        JSSubString sep;
>+        res->getLastMatch(&sep);
>+
>+        result->setResult(sep.length, newIndex);
>+        return true;
>+    }
>+};


>+class SplitStringMatcher {
>+    const jschar *sepChars;
>+    size_t sepLength;
>+  public:

Another blank line.

>+    static const bool returnsCaptures = false;
>+    SplitStringMatcher(JSLinearString *sep) {
>+        sepChars = sep->chars();
>+        sepLength = sep->length();
>+    }
>+    inline bool operator()(JSContext *cx, JSLinearString *str, size_t index,

And again before the operator() definition.

>+                           SplitMatchResult *res) {
>+        JS_ASSERT(index == 0 || index < str->length());
>+        const jschar *chars = str->chars();
>+        jsint match = StringMatch(chars + index, str->length() - index,
>+                                  sepChars, sepLength);

Looks like this would fit in 99 characters if not wrapped.


>+                return false;
>+        }
>+    }
>+    /* Step 9. */
>+    if (limit == 0) {

Blank lines before all steps that aren't grouped together (so before the /* Step 9. */ here).

>+        JSObject *aobj = NewDenseEmptyArray(cx);
>+        if (!aobj)
>+            return false;
>+        vp->setObject(*aobj);
>+        return true;
>+    }
>+    /* Step 10. */
>+    if (sepUndefined) {

Blank line again.


>+    /* Steps 11-15. */
>+    JSObject *aobj;
>+    if (re) {
>+        aobj = SplitHelper(cx, strlin, limit,
>+                           SplitRegExpMatcher(re, cx->regExpStatics()));

This is another 91-character single-liner.


>+        // NB: sepstr is anchored through its storage in vp[2].
>+        aobj = SplitHelper(cx, strlin, limit,
>+                           SplitStringMatcher(sepstr->assertIsLinear()));

Doesn't hurt to assert, I guess, but given that sepstr is a JSLinearString* it seems redundant.


>diff --git a/js/src/tests/ecma_5/String/15.5.4.14-02.js b/js/src/tests/ecma_5/String/15.5.4.14-02.js

>+// from ES5 15.5.4.14
>+assertEqArr("ab".split(/a*?/), ["a", "b"]);
>+assertEqArr("ab".split(/a*/), ["", "b"]);
>+assertEqArr("A<B>bold</B>and<CODE>coded</CODE>".split(/<(\/)?([^<>]+)>/),
>+            ["A", undefined, "B", "bold", "/", "B", "and", undefined,
>+             "CODE", "coded", "/", "CODE", ""]);

We should get in the habit of putting examples in the spec in our tests like this.


>diff --git a/js/src/tests/ecma_5/String/15.5.4.14-03.js b/js/src/tests/ecma_5/String/15.5.4.14-03.js

\o/

Although, these days I have some preference for giving test files meaningful names that at least give the reader a hope in the world of knowing what the test does, and what method/properties/&c. it tests.  Very few people will remember to associate 15.5.4.14 with String.prototype.split, but something like split-xregexp.js has much clearer meaning/contents if you're skimming a file listing.  I'd prefer if you renamed the test files to something like that and split-undefined-separator.js (and maybe split-01.js or something for the test that's a mishmash of tests I mentioned here and examples from the spec -- no unifying concept to put in the name except "split", really).

>diff --git a/js/src/tests/ecma_5/String/jstests.list b/js/src/tests/ecma_5/String/jstests.list

>+script 15.5.4.14-01.js
>+script 15.5.4.14-02.js
>+script 15.5.4.14-03.js
>\ No newline at end of file

Add one, please.  :-)

Nits all, basically -- post a patch with the nits fixed and I can push it tonight.  \o/

Comment 24

[Jan de Mooij [:jandem]]

Attachment: Patch v5

Thanks for the review. I thought SM used 80 characters per line; don't know where I got that from.

Comment 25

[Jan de Mooij [:jandem]]

Attachment: Patch v5b

Move argument evaluation test to split-01.js

Comment 26

[Jeff Walden [:Waldo]]

Comment on attachment 518178 [details] [diff] [review]
Patch v5b

Perfect.  I'll push this to TM later tonight -- don't quite have the time to watch the tree to do it now.

Comment 27

[Jeff Walden [:Waldo]]

Brilliant!

http://hg.mozilla.org/tracemonkey/rev/3b419fbc22ed

Comment 28

[Leon Sorokin]

noticed this hasn't yet been merged into mozilla-central nightly builds; will it be making it into FF4 final?

Comment 29

[Jan de Mooij [:jandem]]

(In reply to comment #28)
> noticed this hasn't yet been merged into mozilla-central nightly builds; will
> it be making it into FF4 final?

Too late for Firefox 4, this will be in Firefox 5.

Comment 30

[Chris Leary [:cdleary] (not checking bugmail)]

http://hg.mozilla.org/mozilla-central/rev/3b419fbc22ed