Last Comment Bug 815431 - (harmony:strrepeat) implement String.prototype.repeat
(harmony:strrepeat)
: implement String.prototype.repeat
Status: RESOLVED FIXED
[mentor=benjamin]
: dev-doc-complete, site-compat
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: unspecified
: All All
: -- normal (vote)
: mozilla24
Assigned To: Sankha Narayan Guria [:sankha]
:
Mentors:
Depends on: 897305
Blocks: es6
  Show dependency treegraph
 
Reported: 2012-11-26 16:14 PST by :Benjamin Peterson
Modified: 2013-08-10 14:54 PDT (History)
14 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Patch (5.27 KB, patch)
2012-12-02 13:10 PST, Max Li [:maxli]
no flags Details | Diff | Splinter Review
WIP Patch with Self-hosted JS (4.79 KB, patch)
2013-05-04 19:20 PDT, Sankha Narayan Guria [:sankha]
benjamin: feedback+
Details | Diff | Splinter Review
patch with comments addressed (4.98 KB, patch)
2013-05-06 09:56 PDT, Sankha Narayan Guria [:sankha]
no flags Details | Diff | Splinter Review
Implements String.prototype.repeat (5.23 KB, patch)
2013-05-06 11:18 PDT, Sankha Narayan Guria [:sankha]
till: review+
Details | Diff | Splinter Review
Final patch passing all tests (6.32 KB, patch)
2013-05-07 20:13 PDT, Sankha Narayan Guria [:sankha]
till: review+
Details | Diff | Splinter Review
Part 2: Optimize String.prototype.repeat (753 bytes, patch)
2013-05-18 01:24 PDT, Sankha Narayan Guria [:sankha]
no flags Details | Diff | Splinter Review

Description :Benjamin Peterson 2012-11-26 16:14:46 PST
The ES6 String.prototype.repeat(n) method returns n concatenated copies of the string.

This is a simple method and would thus be a excellent chance for someone to dive into SpiderMonkey development. Look at String.prototype.contains or String.prototype.startsWith for inspiration.

The latest spec draft can be found at http://wiki.ecmascript.org/doku.php?id=harmony:specification_drafts
Comment 1 Max Li [:maxli] 2012-12-02 13:10:09 PST
Created attachment 687549 [details] [diff] [review]
Patch
Comment 2 :Benjamin Peterson 2012-12-02 13:53:13 PST
Comment on attachment 687549 [details] [diff] [review]
Patch

Review of attachment 687549 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jit-test/tests/basic/string-repeat.js
@@ +4,5 @@
> +assertEq("a".repeat(10), "aaaaaaaaaa");
> +var myobj = {toString : (function () "abc"), repeat : String.prototype.repeat};
> +assertEq(myobj.repeat(1), "abc");
> +assertEq(myobj.repeat(2), "abcabc");
> +

Also need to test:

- zero length repeats
- that the number of repeats is converted to an integer (valueOf) after toString is called on the object
- negative repeat count
- repeat count > possible string size

::: js/src/js.msg
@@ +195,5 @@
>  MSG_DEF(JSMSG_BAD_CLONE_FUNOBJ_SCOPE, 142, 0, JSEXN_TYPEERR, "bad cloned function scope chain")
>  MSG_DEF(JSMSG_SHARPVAR_TOO_BIG,       143, 0, JSEXN_SYNTAXERR, "overlarge sharp variable number")
>  MSG_DEF(JSMSG_ILLEGAL_CHARACTER,      144, 0, JSEXN_SYNTAXERR, "illegal character")
>  MSG_DEF(JSMSG_BAD_OCTAL,              145, 1, JSEXN_SYNTAXERR, "{0} is not a legal ECMA-262 octal constant")
> +MSG_DEF(JSMSG_REPEAT_RANGE,           146, 0, JSEXN_RANGEERR, "argument must be positive")

More specific like "repeat count must be positive" would be better.

::: js/src/jsstr.cpp
@@ +1325,5 @@
> +    // Steps 4 and 5
> +    double nDouble;
> +    if (!ToInteger(cx, args[0], &nDouble))
> +        return false;
> +    

Rm extra whitespace here.

@@ +1337,5 @@
> +
> +    // Step 8
> +    for (unsigned i = 1; i < n; i++) {
> +        RootedString thisStr(cx, ThisToStringForStringProto(cx, args));
> +        str = js_ConcatStrings(cx, str, thisStr);

This is probably not what we want to do, since it means we'll end up allocating |n| objects. A new string of the appropiate length should be created and copied in |n| times.
Comment 3 :Benjamin Peterson 2013-04-28 08:39:28 PDT
Max, I'm unassigning the bug from you, so someone else can work on this if they want. If you're still around, you're of course free to reassign it and update your patch.
Comment 4 Sankha Narayan Guria [:sankha] 2013-04-28 09:19:05 PDT
I would like to work on this.
Comment 5 :Ms2ger (⌚ UTC+1/+2) 2013-04-28 09:23:57 PDT
Comment on attachment 687549 [details] [diff] [review]
Patch

Review of attachment 687549 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsstr.cpp
@@ +1323,5 @@
> +        return false;
> +
> +    // Steps 4 and 5
> +    double nDouble;
> +    if (!ToInteger(cx, args[0], &nDouble))

This doesn't look safe; should be args.get(0) and a test for "foo".repeat() without arguments.

@@ +1327,5 @@
> +    if (!ToInteger(cx, args[0], &nDouble))
> +        return false;
> +    
> +    // Steps 6 and 7
> +    if (nDouble <= 0 || nDouble == js_PositiveInfinity) {

The spec doesn't seem clear about how to handle NaN.
Comment 6 Brandon Benvie [:benvie] 2013-04-29 16:31:26 PDT
(In reply to :Ms2ger from comment #5)
> The spec doesn't seem clear about how to handle NaN.

String.prototype.repeat spec step 4 says "Let n be the result of calling ToInteger(count)", so the empty string.
Comment 7 Sankha Narayan Guria [:sankha] 2013-05-04 19:20:01 PDT
Created attachment 745611 [details] [diff] [review]
WIP Patch with Self-hosted JS

I had discussed about the bug on IRC with Ms2ger and till, and tried this patch as a self hosted JS.
Comment 8 :Benjamin Peterson 2013-05-05 06:31:41 PDT
Comment on attachment 745611 [details] [diff] [review]
WIP Patch with Self-hosted JS

Review of attachment 745611 [details] [diff] [review]:
-----------------------------------------------------------------

I like the self-hosting.

::: js/src/builtin/String.js
@@ +16,5 @@
> +    // Steps 4-5.
> +    var n = ToInteger(count);
> +
> +    // Steps 6-7.
> +    if(n < 0 || n === Number.POSITIVE_INFINITY)

Style: space between if and (. Here and below.

@@ +20,5 @@
> +    if(n < 0 || n === Number.POSITIVE_INFINITY)
> +        ThrowError(JSMSG_REPEAT_RANGE);
> +
> +    // Step 8-9.
> +    if(n === 0)

Brace the body.

::: js/src/jit-test/tests/basic/string-repeat.js
@@ +1,5 @@
> +assertEq("abc".repeat(1), "abc");
> +assertEq("abc".repeat(2), "abcabc");
> +assertEq("abc".repeat(3), "abcabcabc");
> +assertEq("a".repeat(10), "aaaaaaaaaa");
> +var myobj = {toString : (function () "abc"), repeat : String.prototype.repeat};

It's good you're testing the coercion of this. There are need to be tests for;
- The coercion of |count|.
- Invalid |count| arguments.
- .repeat(0)
-  the empty string
Comment 9 Till Schneidereit [:till] (ECOOP July 18 - July 22, pto July 23 - July 31) 2013-05-05 13:39:54 PDT
Comment on attachment 745611 [details] [diff] [review]
WIP Patch with Self-hosted JS

Review of attachment 745611 [details] [diff] [review]:
-----------------------------------------------------------------

Very nice to see this implemented using self-hosting.

That being said, I'm not convinced that the exact implementation is the best we can do.

Instead of splitting the original string and concatting it to a result array which you join at the end, it should be more efficient to build a string rope object that's as close to a balanced tree as feasible. Something along the following (untested) lines doesn't really create a balanced tree, but at least goes into the general direction:

var result = S;
for (var i = 1; i < n; i *= 2)
  result += result;
for (; i < n; i++)
  result += S;

If you're interested, you can find an explanation of how Strings are represented in SpiderMonkey in the introductory comment in vm/String.h.

::: js/src/builtin/String.js
@@ +25,5 @@
> +        return "";
> +    else {
> +        var strArray = callFunction(split, S, '');
> +        var finalArray = [];
> +        for(var i = 0; i < n; i++)

Style: space between for and (.
Comment 10 Sankha Narayan Guria [:sankha] 2013-05-06 09:56:45 PDT
Created attachment 745924 [details] [diff] [review]
patch with comments addressed
Comment 11 Till Schneidereit [:till] (ECOOP July 18 - July 22, pto July 23 - July 31) 2013-05-06 10:14:53 PDT
Comment on attachment 745924 [details] [diff] [review]
patch with comments addressed

Review of attachment 745924 [details] [diff] [review]:
-----------------------------------------------------------------

Very nice! r=me with comments addressed.

::: js/src/builtin/String.js
@@ +22,5 @@
> +
> +    // Step 8-9.
> +    if (n === 0) {
> +        return "";
> +    } else {

You can get rid of the `else` block, here.

@@ +24,5 @@
> +    if (n === 0) {
> +        return "";
> +    } else {
> +        var result = S;
> +        for (var i = 1; i < n / 2; i *= 2)

The condition can be `i <= n`, to reduce the amount of linear additions below.

Ideally, we'd do something a bit more complex to create a rope that's closer to being truly balanced, but we can do that if this ever turns out to be a hot spot in something we care about.

::: js/src/jit-test/tests/basic/string-repeat.js
@@ +9,5 @@
> +try {
> +    "abc".repeat(-1);
> +} catch(error) {
> +    assertEq(error, "repeat count must be positive");
> +}

Can you also add a test for Number.POSITIVE_INFINITY?
Comment 12 :Benjamin Peterson 2013-05-06 10:18:25 PDT
Comment on attachment 745924 [details] [diff] [review]
patch with comments addressed

Review of attachment 745924 [details] [diff] [review]:
-----------------------------------------------------------------

What Till said and another comment.

::: js/src/jit-test/tests/basic/string-repeat.js
@@ +9,5 @@
> +try {
> +    "abc".repeat(-1);
> +} catch(error) {
> +    assertEq(error, "repeat count must be positive");
> +}

This will silently pass if the exception isn't raised. Use one of the functions in lib/asserts.js.
Comment 13 Sankha Narayan Guria [:sankha] 2013-05-06 11:18:49 PDT
Created attachment 745969 [details] [diff] [review]
Implements String.prototype.repeat
Comment 14 Till Schneidereit [:till] (ECOOP July 18 - July 22, pto July 23 - July 31) 2013-05-06 11:25:12 PDT
Comment on attachment 745969 [details] [diff] [review]
Implements String.prototype.repeat

Review of attachment 745969 [details] [diff] [review]:
-----------------------------------------------------------------

Very nice!

(resetting the review for benjamin: one r+ is enough for this.)

::: js/src/jit-test/tests/basic/string-repeat.js
@@ +10,5 @@
> +assertEq(myobj.repeat(1), "abc");
> +assertEq(myobj.repeat(2), "abcabc");
> +assertEq("abc".repeat(0), "");
> +assertThrowsInstanceOf("abc".repeat(-1), RangeError,
> +                       "String.protype.repeat should raise RangeError on negative arguments");

s/protype/prototype/ here and below
Comment 15 :Benjamin Peterson 2013-05-06 11:35:41 PDT
Comment on attachment 745969 [details] [diff] [review]
Implements String.prototype.repeat

Review of attachment 745969 [details] [diff] [review]:
-----------------------------------------------------------------

Have you actually run these tests?
Comment 16 Sankha Narayan Guria [:sankha] 2013-05-06 11:37:34 PDT
No, not yet. I was asking around on IRC about running the jit-tests but didn't get the answer.
Comment 17 Sankha Narayan Guria [:sankha] 2013-05-07 20:13:09 PDT
Created attachment 746736 [details] [diff] [review]
Final patch passing all tests
Comment 18 Till Schneidereit [:till] (ECOOP July 18 - July 22, pto July 23 - July 31) 2013-05-08 02:25:51 PDT
Comment on attachment 746736 [details] [diff] [review]
Final patch passing all tests

Review of attachment 746736 [details] [diff] [review]:
-----------------------------------------------------------------

Nice!

I'll push this after the next merge to Aurora (i.e., next Monday). That way, we'll have some time on Nightly to discover potential web-compat problems as early as possible.
Comment 19 Till Schneidereit [:till] (ECOOP July 18 - July 22, pto July 23 - July 31) 2013-05-13 12:39:22 PDT
https://hg.mozilla.org/integration/mozilla-inbound/rev/95a4ecd8c308
Comment 20 Ed Morley [:emorley] 2013-05-14 05:28:33 PDT
https://hg.mozilla.org/mozilla-central/rev/95a4ecd8c308
Comment 21 pete 2013-05-17 17:47:54 PDT
instead of the trailing:

    for (; i < n; i++)
        result += S;

Wouldn't it be better to use something like (or whatever substr|slice is cheaper):

    result += result.substring(0, S.length*(n-i));
Comment 22 Sankha Narayan Guria [:sankha] 2013-05-18 01:24:41 PDT
Created attachment 751316 [details] [diff] [review]
Part 2: Optimize String.prototype.repeat

I think it will make String.prototype.repeat faster. Here is the patch for the change.
Comment 23 :Benjamin Peterson 2013-05-18 05:50:11 PDT
Please file a new bug.
Comment 24 Till Schneidereit [:till] (ECOOP July 18 - July 22, pto July 23 - July 31) 2013-05-18 09:47:23 PDT
Comment on attachment 751316 [details] [diff] [review]
Part 2: Optimize String.prototype.repeat

Review of attachment 751316 [details] [diff] [review]:
-----------------------------------------------------------------

Benjamin's right: please file a new bug.

Also, it'd be nice to get some measurements on this, as I'm not entirely sure how this'll play out.
Comment 25 Joseph Myers 2013-07-23 21:02:08 PDT
Comment on attachment 751316 [details] [diff] [review]
Part 2: Optimize String.prototype.repeat

This is a string repeating function that I wrote many years ago and which is still the fastest-known JavaScript string repeating function. I suggest that it be used for implementing String.prototype.repeat

function repeat(x, n) {
/* e.g., repeat("abc", 2) === "abcabc" */
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
}

Let me know if you want a benchmark. I will be happy to oblige.

Thanks!

Note You need to log in before you can comment on or make changes to this bug.