Changeset 203147 in webkit

Timestamp:

Jul 12, 2016, 6:25:25 PM (10 years ago)

Author:

benjamin@webkit.org

Message:

[JSC] Array.prototype.join() fails some conformance tests
​https://bugs.webkit.org/show_bug.cgi?id=159657

Patch by Benjamin Poulain <​bpoulain@apple.com> on 2016-07-12
Reviewed by Saam Barati.

Source/JavaScriptCore:

There were a couple of failures:
-separator.toString() was called *before* we get the length

and process ToLength() on it.

-We were using toUInt32() on length instead of ToLength(),

failing on big integers and various negative numbers.

Additionally, I replaced the "fast" ArrayStorage path
by a fully generic implementation that does not depends on StringJoiner.

The reason is StringJoiner was doing poorly on sparse objects
in certain cases.
If you have a sparse object with a length > INT_MAX but very few
indices defined, and you join on the empty string, it should be possible
to join the array (albeit very slowly). With StringJoiner, we fail
because we try to allocate > INT_MAX empty strings in a contiguous vector.

• runtime/ArrayPrototype.cpp:

(JSC::slowJoin):
(JSC::canUseFastJoin):
(JSC::fastJoin):
(JSC::arrayProtoFuncJoin):
(JSC::join): Deleted.

• runtime/JSArray.h:

(JSC::toLength):

Source/WTF:

• wtf/text/AtomicString.cpp:

(WTF::AtomicString::number):

• wtf/text/AtomicString.h:

LayoutTests:

I removed 3 sputnik tests that are incorrect in the latest spec.
In ES5, Array.prototype.join() was using ToUint32 on the argument:

​https://es5.github.io/#x15.4.4.5

In ES6, the function uses ToLength:

​https://tc39.github.io/ecma262/#sec-array.prototype.join

The test use Infinity and very large integer as the length.
They are guaranteed to time out or run out of memory.
Even if we waited the hours it takes to run this, the results would be different
from what the tests expect.

• js/array-join-expected.txt: Added.
• js/array-join.html: Added.
• js/script-tests/array-join.js: Added.

Location:

trunk

Files:

• LayoutTests/ChangeLog (modified) (1 diff)
• LayoutTests/fast/history/replacestate-nocrash.html (modified) (1 diff)
• LayoutTests/js/array-join-expected.txt (added)
• LayoutTests/js/array-join.html (added)
• LayoutTests/js/script-tests/array-join.js (added)
• LayoutTests/sputnik/Conformance/15_Native_Objects/15.4_Array/15.4.4/15.4.4.5_Array_prototype_join/S15.4.4.5_A2_T2-expected.txt (deleted)
• LayoutTests/sputnik/Conformance/15_Native_Objects/15.4_Array/15.4.4/15.4.4.5_Array_prototype_join/S15.4.4.5_A2_T2.html (deleted)
• LayoutTests/sputnik/Conformance/15_Native_Objects/15.4_Array/15.4.4/15.4.4.5_Array_prototype_join/S15.4.4.5_A4_T1-expected.txt (deleted)
• LayoutTests/sputnik/Conformance/15_Native_Objects/15.4_Array/15.4.4/15.4.4.5_Array_prototype_join/S15.4.4.5_A4_T1.html (deleted)
• LayoutTests/sputnik/Conformance/15_Native_Objects/15.4_Array/15.4.4/15.4.4.5_Array_prototype_join/S15.4.4.5_A4_T2-expected.txt (deleted)
• LayoutTests/sputnik/Conformance/15_Native_Objects/15.4_Array/15.4.4/15.4.4.5_Array_prototype_join/S15.4.4.5_A4_T2.html (deleted)
• LayoutTests/sputnik/Conformance/15_Native_Objects/15.4_Array/15.4.4/15.4.4.5_Array_prototype_join/S15.4.4.5_A4_T3.html (modified) (1 diff)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/runtime/ArrayPrototype.cpp (modified) (4 diffs)
• Source/JavaScriptCore/runtime/JSArray.h (modified) (1 diff)
• Source/WTF/ChangeLog (modified) (1 diff)
• Source/WTF/wtf/text/AtomicString.cpp (modified) (2 diffs)
• Source/WTF/wtf/text/AtomicString.h (modified) (1 diff)

trunk/LayoutTests/ChangeLog

@@ +1 @@
+2016-07-12  Benjamin Poulain  <bpoulain@apple.com>
+
+        [JSC] Array.prototype.join() fails some conformance tests
+        https://bugs.webkit.org/show_bug.cgi?id=159657
+
+        Reviewed by Saam Barati.
+
+        I removed 3 sputnik tests that are incorrect in the latest spec.
+        In ES5, Array.prototype.join() was using ToUint32 on the argument:
+            https://es5.github.io/#x15.4.4.5
+        In ES6, the function uses ToLength:
+            https://tc39.github.io/ecma262/#sec-array.prototype.join
+
+        The test use Infinity and very large integer as the length.
+        They are guaranteed to time out or run out of memory.
+        Even if we waited the hours it takes to run this, the results would be different
+        from what the tests expect.
+
+        * js/array-join-expected.txt: Added.
+        * js/array-join.html: Added.
+        * js/script-tests/array-join.js: Added.
+
 2016-07-12  Commit Queue  <commit-queue@webkit.org>
 

trunk/LayoutTests/fast/history/replacestate-nocrash.html

@@ -7 +7 @@
 
 Object.prototype.__defineSetter__("foo",function(){history.replaceState("")});
-history.replaceState({foo:1,zzz:Array(1<<22).join("a")});
+history.replaceState({foo:1,zzz:"a".repeat(1<<22)});
 history.state.length;
 </script>

trunk/LayoutTests/sputnik/Conformance/15_Native_Objects/15.4_Array/15.4.4/15.4.4.5_Array_prototype_join/S15.4.4.5_A4_T3.html

@@ -81 +81 @@
 
 //CHECK#1
-if (obj.join("") !== "xy") {
-  testFailed('#1: var obj = {}; obj.join = Array.prototype.join; obj[0] = "x"; obj[1] = "y"; obj[2] = "z"; obj.length = -4294967294; obj.join("") === "xy". Actual: ' + (obj.join("")));
+if (obj.join("") !== "") {
+  testFailed('#1: var obj = {}; obj.join = Array.prototype.join; obj[0] = "x"; obj[1] = "y"; obj[2] = "z"; obj.length = -4294967294; obj.join("") === "". Actual: ' + (obj.join("")));
 }
 

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2016-07-12  Benjamin Poulain  <bpoulain@apple.com>
+
+        [JSC] Array.prototype.join() fails some conformance tests
+        https://bugs.webkit.org/show_bug.cgi?id=159657
+
+        Reviewed by Saam Barati.
+
+        There were a couple of failures:
+        -separator.toString() was called *before* we get the length
+         and process ToLength() on it.
+        -We were using toUInt32() on length instead of ToLength(),
+         failing on big integers and various negative numbers.
+
+        Additionally, I replaced the "fast" ArrayStorage path
+        by a fully generic implementation that does not depends on StringJoiner.
+
+        The reason is StringJoiner was doing poorly on sparse objects
+        in certain cases.
+        If you have a sparse object with a length > INT_MAX but very few
+        indices defined, and you join on the empty string, it should be possible
+        to join the array (albeit very slowly). With StringJoiner, we fail
+        because we try to allocate > INT_MAX empty strings in a contiguous vector.
+
+        * runtime/ArrayPrototype.cpp:
+        (JSC::slowJoin):
+        (JSC::canUseFastJoin):
+        (JSC::fastJoin):
+        (JSC::arrayProtoFuncJoin):
+        (JSC::join): Deleted.
+        * runtime/JSArray.h:
+        (JSC::toLength):
+
 2016-07-12  Mark Lam  <mark.lam@apple.com>
 

trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp

@@ -487 +487 @@
 }
 
-static inline JSValue join(ExecState& state, JSObject* thisObject, StringView separator)
-{
-    unsigned length = getLength(&state, thisObject);
-    if (state.hadException())
-        return jsUndefined();
-
+static JSValue slowJoin(ExecState& exec, JSObject* thisObject, JSString* separator, uint64_t length)
+{
+    // 5. If len is zero, return the empty String.
+    if (!length)
+        return jsEmptyString(&exec);
+
+    VM& vm = exec.vm();
+
+    // 6. Let element0 be Get(O, "0").
+    JSValue element0 = thisObject->getIndex(&exec, 0);
+    if (vm.exception())
+        return JSValue();
+
+    // 7. If element0 is undefined or null, let R be the empty String; otherwise, let R be ? ToString(element0).
+    JSString* r = nullptr;
+    if (element0.isUndefinedOrNull())
+        r = jsEmptyString(&exec);
+    else
+        r = element0.toString(&exec);
+    if (vm.exception())
+        return JSValue();
+
+    // 8. Let k be 1.
+    // 9. Repeat, while k < len
+    // 9.e Increase k by 1..
+    for (uint64_t k = 1; k < length; ++k) {
+        // b. Let element be ? Get(O, ! ToString(k)).
+        JSValue element = thisObject->get(&exec, Identifier::fromString(&exec, AtomicString::number(k)));
+        if (vm.exception())
+            return JSValue();
+
+        // c. If element is undefined or null, let next be the empty String; otherwise, let next be ? ToString(element).
+        JSString* next = nullptr;
+        if (element.isUndefinedOrNull()) {
+            if (!separator->length())
+                continue;
+            next = jsEmptyString(&exec);
+        } else
+            next = element.toString(&exec);
+        if (vm.exception())
+            return JSValue();
+
+        // a. Let S be the String value produced by concatenating R and sep.
+        // d. Let R be a String value produced by concatenating S and next.
+        r = JSRopeString::create(vm, r, separator, next);
+    }
+    // 10. Return R.
+    return r;
+}
+
+static inline bool canUseFastJoin(const JSObject* thisObject)
+{
+    switch (thisObject->indexingType()) {
+    case ALL_CONTIGUOUS_INDEXING_TYPES:
+    case ALL_INT32_INDEXING_TYPES:
+    case ALL_DOUBLE_INDEXING_TYPES:
+        return true;
+    default:
+        break;
+    }
+    return false;
+}
+
+static inline JSValue fastJoin(ExecState& state, JSObject* thisObject, StringView separator, unsigned length)
+{
     switch (thisObject->indexingType()) {
     case ALL_CONTIGUOUS_INDEXING_TYPES:
@@ -543 +602 @@
         return joiner.join(state);
     }
-    case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
-        auto& storage = *thisObject->butterfly()->arrayStorage();
-        if (length > storage.vectorLength())
-            break;
-        if (storage.hasHoles() && thisObject->structure(state.vm())->holesMustForwardToPrototype(state.vm()))
-            break;
-        JSStringJoiner joiner(state, separator, length);
-        if (state.hadException())
-            return jsUndefined();
-        auto data = storage.vector().data();
-        for (unsigned i = 0; i < length; ++i) {
-            if (JSValue value = data[i].get()) {
-                if (!joiner.appendWithoutSideEffects(state, value))
-                    goto generalCase;
-            } else
-                joiner.appendEmptyString();
-        }
-        return joiner.join(state);
-    }
     }
 
@@ -581 +621 @@
 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec)
 {
+    // 1. Let O be ? ToObject(this value).
     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
     if (!thisObject)
@@ -589 +630 @@
         return JSValue::encode(earlyReturnValue);
 
+    // 2. Let len be ? ToLength(? Get(O, "length")).
+    double length = toLength(exec, thisObject);
+    if (exec->hadException())
+        return JSValue::encode(JSValue());
+
+    // 3. If separator is undefined, let separator be the single-element String ",".
     JSValue separatorValue = exec->argument(0);
     if (separatorValue.isUndefined()) {
         const LChar comma = ',';
-        return JSValue::encode(join(*exec, thisObject, { &comma, 1 }));
-    }
-
-    JSString* separator = separatorValue.toString(exec);
+
+        if (UNLIKELY(length > std::numeric_limits<unsigned>::max() || !canUseFastJoin(thisObject))) {
+            uint64_t length64 = static_cast<uint64_t>(length);
+            ASSERT(static_cast<double>(length64) == length);
+            JSString* jsSeparator = jsSingleCharacterString(exec, comma);
+            if (exec->hadException())
+                return JSValue::encode(JSValue());
+
+            return JSValue::encode(slowJoin(*exec, thisObject, jsSeparator, length64));
+        }
+
+        unsigned unsignedLength = static_cast<unsigned>(length);
+        ASSERT(static_cast<double>(unsignedLength) == length);
+        return JSValue::encode(fastJoin(*exec, thisObject, { &comma, 1 }, unsignedLength));
+    }
+
+    // 4. Let sep be ? ToString(separator).
+    JSString* jsSeparator = separatorValue.toString(exec);
     if (exec->hadException())
         return JSValue::encode(jsUndefined());
-    return JSValue::encode(join(*exec, thisObject, separator->view(exec).get()));
+
+    if (UNLIKELY(length > std::numeric_limits<unsigned>::max() || !canUseFastJoin(thisObject))) {
+        uint64_t length64 = static_cast<uint64_t>(length);
+        ASSERT(static_cast<double>(length64) == length);
+        return JSValue::encode(slowJoin(*exec, thisObject, jsSeparator, length64));
+    }
+
+    return JSValue::encode(fastJoin(*exec, thisObject, jsSeparator->view(exec).get(), length));
 }
 

trunk/Source/JavaScriptCore/runtime/JSArray.h

@@ -354 +354 @@
 }
 
+ALWAYS_INLINE double toLength(ExecState* exec, JSObject* obj)
+{
+    if (isJSArray(obj))
+        return jsCast<JSArray*>(obj)->length();
+
+    VM& vm = exec->vm();
+    JSValue lengthValue = obj->get(exec, vm.propertyNames->length);
+    if (UNLIKELY(vm.exception()))
+        return PNaN;
+    return lengthValue.toLength(exec);
+}
+
 } // namespace JSC
 

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2016-07-12  Benjamin Poulain  <bpoulain@apple.com>
+
+        [JSC] Array.prototype.join() fails some conformance tests
+        https://bugs.webkit.org/show_bug.cgi?id=159657
+
+        Reviewed by Saam Barati.
+
+        * wtf/text/AtomicString.cpp:
+        (WTF::AtomicString::number):
+        * wtf/text/AtomicString.h:
+
 2016-07-12  Commit Queue  <commit-queue@webkit.org>
 

trunk/Source/WTF/wtf/text/AtomicString.cpp

@@ -1 +1 @@
 /*
- * Copyright (C) 2004-2008, 2013-2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2004-2008, 2013-2014, 2016 Apple Inc. All rights reserved.
  * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com>
  * Copyright (C) 2012 Google Inc. All rights reserved.
@@ -93 +93 @@
 }
 
+AtomicString AtomicString::number(unsigned long number)
+{
+    return numberToStringUnsigned<AtomicString>(number);
+}
+
+AtomicString AtomicString::number(unsigned long long number)
+{
+    return numberToStringUnsigned<AtomicString>(number);
+}
+
 AtomicString AtomicString::number(double number)
 {

trunk/Source/WTF/wtf/text/AtomicString.h

@@ -106 +106 @@
     WTF_EXPORT_STRING_API static AtomicString number(int);
     WTF_EXPORT_STRING_API static AtomicString number(unsigned);
+    WTF_EXPORT_STRING_API static AtomicString number(unsigned long);
+    WTF_EXPORT_STRING_API static AtomicString number(unsigned long long);
     WTF_EXPORT_STRING_API static AtomicString number(double);
     // If we need more overloads of the number function, we can add all the others that String has, but these seem to do for now.