:Benjamin Peterson Reporter
	Description • 12 years ago

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

	:Benjamin Peterson Reporter
	Comment 2 • 12 years ago

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.

	:Benjamin Peterson Reporter
	Comment 3 • 11 years ago

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.

	Sankha Narayan Guria [:sankha] Assignee
	Comment 4 • 11 years ago

I would like to work on this.

	:Ms2ger (he/him; ⌚ UTC+1/+2)
	Comment 5 • 11 years ago

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.

	Brandon Benvie [:benvie]
	Comment 6 • 11 years ago

(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.

	Sankha Narayan Guria [:sankha] Assignee
	Comment 7 • 11 years ago

I had discussed about the bug on IRC with Ms2ger and till, and tried this patch as a self hosted JS.

	:Benjamin Peterson Reporter
	Comment 8 • 11 years ago

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

	Till Schneidereit [:till]
	Comment 9 • 11 years ago

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 (.

	Till Schneidereit [:till]
	Comment 11 • 11 years ago

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?

	:Benjamin Peterson Reporter
	Comment 12 • 11 years ago

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.

	Till Schneidereit [:till]
	Comment 14 • 11 years ago

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

	:Benjamin Peterson Reporter
	Comment 15 • 11 years ago

Comment on attachment 745969 [details] [diff] [review]
Implements String.prototype.repeat

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

Have you actually run these tests?

	Sankha Narayan Guria [:sankha] Assignee
	Comment 16 • 11 years ago

No, not yet. I was asking around on IRC about running the jit-tests but didn't get the answer.

	Till Schneidereit [:till]
	Comment 18 • 11 years ago

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.

	Till Schneidereit [:till]
	Comment 19 • 11 years ago

https://hg.mozilla.org/integration/mozilla-inbound/rev/95a4ecd8c308

	Ed Morley [:emorley]
	Comment 20 • 11 years ago

https://hg.mozilla.org/mozilla-central/rev/95a4ecd8c308

	pete
	Comment 21 • 11 years ago

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));

	Sankha Narayan Guria [:sankha] Assignee
	Comment 22 • 11 years ago

I think it will make String.prototype.repeat faster. Here is the patch for the change.

	:Benjamin Peterson Reporter
	Comment 23 • 11 years ago

Please file a new bug.

	Till Schneidereit [:till]
	Comment 24 • 11 years ago

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.

	Joseph Myers
	Comment 25 • 11 years ago

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!

	Kohei Yoshino [:kohei]
	Comment 26 • 11 years ago

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/repeat
https://developer.mozilla.org/ja/docs/Site_Compatibility_for_Firefox_24