Changeset 198838 in webkit for trunk/Source/JavaScriptCore/builtins

Timestamp:

Mar 30, 2016, 9:34:30 AM (9 years ago)

Author:

Yusuke Suzuki

Message:

[JSC] Implement String.prototype.repeat in builtins JS
​https://bugs.webkit.org/show_bug.cgi?id=155974

Reviewed by Darin Adler.

Source/JavaScriptCore:

This patch converts C++ String.prototype.repeat implementation into JS builtins.
|this| in strict mode is correctly inferred as String[1]. This fact encourages us
to write PrimitiveTypes.prototype.XXX methods in builtin JS.

LayoutTests/js/string-repeat.html already covers the tests for this change.

Note: String.prototype.repeat functionality is similar to Harmony's
String.prototype.{padStart, padEnd}. It's nice to port them to builtin JS in
the other patch.

The existing C++ code has the fast path for singleCharacterString repeating.
Since this use is important (e.g. generating N length spaces: ' '.repeat(N)),
we keep this fast path as @repeatCharacter().

The performance results show that, while the performance of the single character fast path
is neutral, other string repeating has significant speed up.
There are two reasons.

1. Not resolving string rope.

We added several tests postfixed "not-resolving". In that tests, we do not touch the content
of the generated string. As a result, the generated rope is not resolved.

2. O(log N) intermediate JSRopeStrings.

In the existing C++ implementation, we use JSString::RopeBuilder. We iterate N times and append
the given string to the builder.
In this case, the intermediate rope strings generated in JSString::RopeBuilder is O(N).
In JS builtin implementation, we only iterate log N times. As a result, the number of the
intermediate rope strings becomes O(log N).

[1]: ​http://trac.webkit.org/changeset/195938

• builtins/StringPrototype.js:

(repeatSlowPath):
(repeat):

• bytecode/BytecodeIntrinsicRegistry.cpp:

(JSC::BytecodeIntrinsicRegistry::BytecodeIntrinsicRegistry):

• bytecode/BytecodeIntrinsicRegistry.h:
• runtime/CommonIdentifiers.h:
• runtime/JSGlobalObject.cpp:

(JSC::JSGlobalObject::init):

• runtime/StringPrototype.cpp:

(JSC::stringProtoFuncRepeatCharacter):
(JSC::StringPrototype::finishCreation): Deleted.
(JSC::stringProtoFuncRepeat): Deleted.

• runtime/StringPrototype.h:
• tests/stress/string-repeat-edge-cases.js: Added.

(shouldBe):
(let.object.toString):
(valueOf):
(shouldThrow):

LayoutTests:

Update the error messages.

• js/regress/script-tests/string-repeat-not-resolving-fixed.js: Added.

(test):

• js/regress/script-tests/string-repeat-not-resolving-no-inline.js: Added.

(test):

• js/regress/script-tests/string-repeat-not-resolving.js: Added.

(test):

• js/regress/script-tests/string-repeat-resolving-fixed.js: Added.

(test):

• js/regress/script-tests/string-repeat-resolving-no-inline.js: Added.

(test):

• js/regress/script-tests/string-repeat-resolving.js: Added.

(test):

• js/regress/script-tests/string-repeat-single-not-resolving.js: Added.

(test):

• js/regress/script-tests/string-repeat-single-resolving.js: Added.

(test):

• js/regress/script-tests/string-repeat-small-not-resolving.js: Added.

(test):

• js/regress/script-tests/string-repeat-small-resolving.js: Added.

(test):

• js/regress/string-repeat-not-resolving-expected.txt: Added.
• js/regress/string-repeat-not-resolving-fixed-expected.txt: Added.
• js/regress/string-repeat-not-resolving-fixed.html: Added.
• js/regress/string-repeat-not-resolving-noinline-expected.txt: Added.
• js/regress/string-repeat-not-resolving-noinline.html: Added.
• js/regress/string-repeat-not-resolving.html: Added.
• js/regress/string-repeat-resolving-expected.txt: Added.
• js/regress/string-repeat-resolving-fixed-expected.txt: Added.
• js/regress/string-repeat-resolving-fixed.html: Added.
• js/regress/string-repeat-resolving-no-inline-expected.txt: Added.
• js/regress/string-repeat-resolving-no-inline.html: Added.
• js/regress/string-repeat-resolving.html: Added.
• js/regress/string-repeat-single-not-resolving-expected.txt: Added.
• js/regress/string-repeat-single-not-resolving.html: Added.
• js/regress/string-repeat-single-resolving-expected.txt: Added.
• js/regress/string-repeat-single-resolving.html: Added.
• js/regress/string-repeat-small-not-resolving-expected.txt: Added.
• js/regress/string-repeat-small-not-resolving.html: Added.
• js/regress/string-repeat-small-resolving-expected.txt: Added.
• js/regress/string-repeat-small-resolving.html: Added.
• js/script-tests/string-repeat.js:
• js/string-repeat-expected.txt:

File:

• trunk/Source/JavaScriptCore/builtins/StringPrototype.js (modified) (1 diff)

trunk/Source/JavaScriptCore/builtins/StringPrototype.js

@@ -66 +66 @@
     return createdRegExp[@symbolSearch](thisString);
 }
+
+function repeatSlowPath(string, count)
+{
+    "use strict";
+
+    var repeatCount = @toInteger(count);
+    if (repeatCount < 0 || repeatCount === @Infinity)
+        throw new @RangeError("String.prototype.repeat argument must be greater than or equal to 0 and not be infinity");
+
+    // Return an empty string.
+    if (repeatCount === 0 || string.length === 0)
+        return "";
+
+    // Return the original string.
+    if (repeatCount === 1)
+        return string;
+
+    if (string.length * repeatCount > @MAX_STRING_LENGTH)
+        throw new @Error("Out of memory");
+
+    if (string.length === 1) {
+        // Here, |repeatCount| is always Int32.
+        return @repeatCharacter(string, repeatCount);
+    }
+
+    // Bit operation onto |repeatCount| is safe because |repeatCount| should be within Int32 range,
+    // Repeat log N times to generate the repeated string rope.
+    var result = "";
+    var operand = string;
+    while (true) {
+        if (repeatCount & 1)
+            result += operand;
+        repeatCount >>= 1;
+        if (!repeatCount)
+            return result;
+        operand += operand;
+    }
+}
+
+function repeat(count)
+{
+    "use strict";
+
+    if (this == null) {
+        var message = "String.prototype.repeat requires that |this| not be undefined";
+        if (this === null)
+            message = "String.prototype.repeat requires that |this| not be null";
+        throw new @TypeError(message);
+    }
+
+    var string = @toString(this);
+    if (string.length === 1) {
+        var result = @repeatCharacter(string, count);
+        if (result !== null)
+            return result;
+    }
+
+    return @repeatSlowPath(string, count);
+}