LibJS: Implement Array.prototype.sort()

4 files changed, 368 insertions, 0 deletions

diff --git a/Libraries/LibJS/Runtime/ArrayPrototype.cpp b/Libraries/LibJS/Runtime/ArrayPrototype.cpp
index 0afdbb2436..fab8073fd7 100644
--- a/Libraries/LibJS/Runtime/ArrayPrototype.cpp
+++ b/Libraries/LibJS/Runtime/ArrayPrototype.cpp
@@ -70,6 +70,7 @@ void ArrayPrototype::initialize(GlobalObject& global_object)
     define_native_function(vm.names.reduce, reduce, 1, attr);
     define_native_function(vm.names.reduceRight, reduce_right, 1, attr);
     define_native_function(vm.names.reverse, reverse, 0, attr);
+    define_native_function(vm.names.sort, sort, 1, attr);
     define_native_function(vm.names.lastIndexOf, last_index_of, 1, attr);
     define_native_function(vm.names.includes, includes, 1, attr);
     define_native_function(vm.names.find, find, 1, attr);
@@ -600,6 +601,167 @@ JS_DEFINE_NATIVE_FUNCTION(ArrayPrototype::reverse)
     return array;
 }
 
+static void array_merge_sort(VM& vm, GlobalObject& global_object, Function* compare_func, MarkedValueList& arr_to_sort)
+{
+    // FIXME: it would probably be better to switch to insertion sort for small arrays for
+    // better performance
+    if (arr_to_sort.size() <= 1)
+        return;
+
+    MarkedValueList left(vm.heap());
+    MarkedValueList right(vm.heap());
+
+    left.ensure_capacity(arr_to_sort.size() / 2);
+    right.ensure_capacity(arr_to_sort.size() / 2 + (arr_to_sort.size() & 1));
+
+    for (size_t i = 0; i < arr_to_sort.size(); ++i) {
+        if (i < arr_to_sort.size() / 2) {
+            left.append(arr_to_sort[i]);
+        } else {
+            right.append(arr_to_sort[i]);
+        }
+    }
+
+    array_merge_sort(vm, global_object, compare_func, left);
+    if (vm.exception())
+        return;
+    array_merge_sort(vm, global_object, compare_func, right);
+    if (vm.exception())
+        return;
+
+    arr_to_sort.clear();
+
+    size_t left_index = 0, right_index = 0;
+
+    while (left_index < left.size() && right_index < right.size()) {
+        auto x = left[left_index];
+        auto y = right[right_index];
+
+        double comparison_result;
+
+        if (x.is_undefined() && y.is_undefined()) {
+            comparison_result = 0;
+        } else if (x.is_undefined()) {
+            comparison_result = 1;
+        } else if (y.is_undefined()) {
+            comparison_result = -1;
+        } else if (compare_func) {
+            auto call_result = vm.call(*compare_func, js_undefined(), left[left_index], right[right_index]);
+            if (vm.exception())
+                return;
+
+            if (call_result.is_nan()) {
+                comparison_result = 0;
+            } else {
+                comparison_result = call_result.to_double(global_object);
+                if (vm.exception())
+                    return;
+            }
+        } else {
+            // FIXME: It would probably be much better to be smarter about this and implement
+            // the Abstract Relational Comparison in line once iterating over code points, rather
+            // than calling it twice after creating two primitive strings.
+
+            auto x_string = x.to_primitive_string(global_object);
+            if (vm.exception())
+                return;
+            auto y_string = y.to_primitive_string(global_object);
+            if (vm.exception())
+                return;
+
+            auto x_string_value = Value(x_string);
+            auto y_string_value = Value(y_string);
+
+            // Because they are called with primitive strings, these abstract_relation calls
+            // should never result in a VM exception.
+            auto x_lt_y_relation = abstract_relation(global_object, true, x_string_value, y_string_value);
+            ASSERT(x_lt_y_relation != TriState::Unknown);
+            auto y_lt_x_relation = abstract_relation(global_object, true, y_string_value, x_string_value);
+            ASSERT(y_lt_x_relation != TriState::Unknown);
+
+            if (x_lt_y_relation == TriState::True) {
+                comparison_result = -1;
+            } else if (y_lt_x_relation == TriState::True) {
+                comparison_result = 1;
+            } else {
+                comparison_result = 0;
+            }
+        }
+
+        if (comparison_result <= 0) {
+            arr_to_sort.append(left[left_index]);
+            left_index++;
+        } else {
+            arr_to_sort.append(right[right_index]);
+            right_index++;
+        }
+    }
+
+    while (left_index < left.size()) {
+        arr_to_sort.append(left[left_index]);
+        left_index++;
+    }
+
+    while (right_index < right.size()) {
+        arr_to_sort.append(right[right_index]);
+        right_index++;
+    }
+}
+
+JS_DEFINE_NATIVE_FUNCTION(ArrayPrototype::sort)
+{
+    auto* array = vm.this_value(global_object).to_object(global_object);
+    if (vm.exception())
+        return {};
+
+    auto callback = vm.argument(0);
+    if (!callback.is_undefined() && !callback.is_function()) {
+        vm.throw_exception<TypeError>(global_object, ErrorType::NotAFunction, callback.to_string_without_side_effects());
+        return {};
+    }
+
+    auto original_length = get_length(vm, *array);
+    if (vm.exception())
+        return {};
+
+    MarkedValueList values_to_sort(vm.heap());
+
+    for (size_t i = 0; i < original_length; ++i) {
+        auto element_val = array->get(i);
+        if (vm.exception())
+            return {};
+
+        if (!element_val.is_empty())
+            values_to_sort.append(element_val);
+    }
+
+    // Perform sorting by merge sort. This isn't as efficient compared to quick sort, but
+    // quicksort can't be used in all cases because the spec requires Array.prototype.sort()
+    // to be stable. FIXME: when initially scanning through the array, maintain a flag
+    // for if an unstable sort would be indistinguishable from a stable sort (such as just
+    // just strings or numbers), and in that case use quick sort instead for better performance.
+    array_merge_sort(vm, global_object, callback.is_undefined() ? nullptr : &callback.as_function(), values_to_sort);
+    if (vm.exception())
+        return {};
+
+    for (size_t i = 0; i < values_to_sort.size(); ++i) {
+        array->put(i, values_to_sort[i]);
+        if (vm.exception())
+            return {};
+    }
+
+    // The empty parts of the array are always sorted to the end, regardless of the
+    // compare function. FIXME: For performance, a similar process could be used
+    // for undefined, which are sorted to right before the empty values.
+    for (size_t i = values_to_sort.size(); i < original_length; ++i) {
+        array->delete_property(i);
+        if (vm.exception())
+            return {};
+    }
+
+    return array;
+}
+
 JS_DEFINE_NATIVE_FUNCTION(ArrayPrototype::last_index_of)
 {
     auto* this_object = vm.this_value(global_object).to_object(global_object);
diff --git a/Libraries/LibJS/Runtime/ArrayPrototype.h b/Libraries/LibJS/Runtime/ArrayPrototype.h
index 0632650481..bbdb82903e 100644
--- a/Libraries/LibJS/Runtime/ArrayPrototype.h
+++ b/Libraries/LibJS/Runtime/ArrayPrototype.h
@@ -56,6 +56,7 @@ private:
     JS_DECLARE_NATIVE_FUNCTION(reduce);
     JS_DECLARE_NATIVE_FUNCTION(reduce_right);
     JS_DECLARE_NATIVE_FUNCTION(reverse);
+    JS_DECLARE_NATIVE_FUNCTION(sort);
     JS_DECLARE_NATIVE_FUNCTION(last_index_of);
     JS_DECLARE_NATIVE_FUNCTION(includes);
     JS_DECLARE_NATIVE_FUNCTION(find);
diff --git a/Libraries/LibJS/Runtime/CommonPropertyNames.h b/Libraries/LibJS/Runtime/CommonPropertyNames.h
index c9a31bd467..3e92dce93c 100644
--- a/Libraries/LibJS/Runtime/CommonPropertyNames.h
+++ b/Libraries/LibJS/Runtime/CommonPropertyNames.h
@@ -194,6 +194,7 @@ namespace JS {
     P(sin)                                   \
     P(slice)                                 \
     P(some)                                  \
+    P(sort)                                  \
     P(source)                                \
     P(splice)                                \
     P(sqrt)                                  \
diff --git a/Libraries/LibJS/Tests/builtins/Array/Array.prototype.sort.js b/Libraries/LibJS/Tests/builtins/Array/Array.prototype.sort.js
new file mode 100644
index 0000000000..d32c85b4fa
--- /dev/null
+++ b/Libraries/LibJS/Tests/builtins/Array/Array.prototype.sort.js
@@ -0,0 +1,204 @@
+describe("Array.prototype.sort", () => {
+    test("basic functionality", () => {
+        expect(Array.prototype.sort).toHaveLength(1);
+
+        var arr = ["c", "b", "d", "a"];
+        expect(arr.sort()).toEqual(arr);
+        expect(arr).toEqual(["a", "b", "c", "d"]);
+
+        arr = ["aa", "a"];
+        expect(arr.sort()).toEqual(arr);
+        expect(arr).toEqual(["a", "aa"]);
+
+        arr = [1, 0];
+        expect(arr.sort()).toBe(arr); // should be exactly same object
+        expect(arr).toEqual([0, 1]);
+
+        // numbers are sorted as strings
+        arr = [205, -123, 22, 200, 3, -20, -2, -1, 25, 2, 0, 1];
+        expect(arr.sort()).toEqual([-1, -123, -2, -20, 0, 1, 2, 200, 205, 22, 25, 3]);
+
+        // mix of data, including empty slots and undefined
+        arr = ["2", Infinity, null, null, , undefined, 5, , undefined, null, 54, "5"];
+        expect(arr.sort()).toEqual([
+            "2",
+            5,
+            "5",
+            54,
+            Infinity,
+            null,
+            null,
+            null,
+            undefined,
+            undefined,
+            ,
+            ,
+        ]);
+        expect(arr.length).toEqual(12);
+
+        // undefined compare function
+        arr = ["2", Infinity, null, null, , undefined, 5n, , undefined, null, 54, "5"];
+        expect(arr.sort(undefined)).toEqual([
+            "2",
+            5n,
+            "5",
+            54,
+            Infinity,
+            null,
+            null,
+            null,
+            undefined,
+            undefined,
+            ,
+            ,
+        ]);
+        expect(arr.length).toEqual(12);
+
+        // numeric data with compare function to sort numerically
+        arr = [50, 500, 5, Infinity, -Infinity, 0, 10, -10, 1, -1, 5, 0, 15, Infinity];
+        expect(arr.sort((a, b) => a - b)).toEqual([
+            -Infinity,
+            -10,
+            -1,
+            0,
+            0,
+            1,
+            5,
+            5,
+            10,
+            15,
+            50,
+            500,
+            Infinity,
+            Infinity,
+        ]);
+        expect(arr.length).toEqual(14);
+
+        // numeric data with compare function to sort reverse numerically
+        arr = [50, 500, 5, Infinity, -Infinity, 0, 10, -10, 1, -1, 5, 0, 15, Infinity];
+        expect(arr.sort((a, b) => b - a)).toEqual([
+            Infinity,
+            Infinity,
+            500,
+            50,
+            15,
+            10,
+            5,
+            5,
+            1,
+            0,
+            0,
+            -1,
+            -10,
+            -Infinity,
+        ]);
+
+        // small/edge cases
+        expect([].sort()).toEqual([]);
+        expect([5].sort()).toEqual([5]);
+        expect([5, 5].sort()).toEqual([5, 5]);
+        expect([undefined].sort()).toEqual([undefined]);
+        expect([undefined, undefined].sort()).toEqual([undefined, undefined]);
+        expect([,].sort()).toEqual([,]);
+        expect([, ,].sort()).toEqual([, ,]);
+        expect([5, ,].sort()).toEqual([5, ,]);
+        expect([, , 5].sort()).toEqual([5, , ,]);
+
+        // sorting should be stable
+        arr = [
+            { sorted_key: 2, other_property: 1 },
+            { sorted_key: 2, other_property: 2 },
+            { sorted_key: 1, other_property: 3 },
+        ];
+        arr.sort((a, b) => a.sorted_key - b.sorted_key);
+        expect(arr[1].other_property == 1);
+        expect(arr[2].other_property == 2);
+    });
+
+    test("that it makes no unnecessary calls to compare function", () => {
+        expectNoCallCompareFunction = function (a, b) {
+            expect().fail();
+        };
+
+        expect([].sort(expectNoCallCompareFunction)).toEqual([]);
+        expect([1].sort(expectNoCallCompareFunction)).toEqual([1]);
+        expect([1, undefined].sort(expectNoCallCompareFunction)).toEqual([1, undefined]);
+        expect([undefined, undefined].sort(expectNoCallCompareFunction)).toEqual([
+            undefined,
+            undefined,
+        ]);
+        expect([, , 1, ,].sort(expectNoCallCompareFunction)).toEqual([1, , , ,]);
+        expect([undefined, , 1, , undefined, ,].sort(expectNoCallCompareFunction)).toEqual([
+            1,
+            undefined,
+            undefined,
+            ,
+            ,
+            ,
+        ]);
+    });
+
+    test("that it works on non-arrays", () => {
+        var obj = { length: 0 };
+        expect(Array.prototype.sort.call(obj)).toBe(obj);
+        expect(obj).toEqual({ length: 0 });
+
+        obj = { 0: 1, length: 0 };
+        expect(Array.prototype.sort.call(obj, undefined)).toBe(obj);
+        expect(obj).toEqual({ 0: 1, length: 0 });
+
+        obj = { 0: 3, 1: 2, 2: 1, 3: 0, length: 2 };
+        expect(Array.prototype.sort.call(obj)).toBe(obj);
+        expect(obj).toEqual({ 0: 2, 1: 3, 2: 1, 3: 0, length: 2 });
+
+        obj = { 0: 3, 1: 2, 2: 1, a: "b", hello: "friends!", length: 2 };
+        expect(Array.prototype.sort.call(obj)).toBe(obj);
+        expect(obj).toEqual({ 0: 2, 1: 3, 2: 1, 3: 0, a: "b", hello: "friends!", length: 2 });
+
+        obj = { 0: 2, 1: 3, 2: 1, a: "b", hello: "friends!", length: 2 };
+        expect(
+            Array.prototype.sort.call(obj, (a, b) => {
+                expect(a == 2 || a == 3).toBeTrue();
+                expect(b == 2 || b == 3).toBeTrue();
+                return b - a;
+            })
+        ).toBe(obj);
+        expect(obj).toEqual({ 0: 3, 1: 2, 2: 1, 3: 0, a: "b", hello: "friends!", length: 2 });
+    });
+
+    test("that it handles abrupt completions correctly", () => {
+        class TestError extends Error {
+            constructor() {
+                super();
+                this.name = "TestError";
+            }
+        }
+
+        arr = [1, 2, 3];
+        expect(() =>
+            arr.sort((a, b) => {
+                throw new TestError();
+            })
+        ).toThrow(TestError);
+
+        class DangerousToString {
+            toString() {
+                throw new TestError();
+            }
+        }
+        arr = [new DangerousToString(), new DangerousToString()];
+        expect(() => arr.sort()).toThrow(TestError);
+    });
+
+    test("that it does not use deleteProperty unnecesarily", () => {
+        var obj = new Proxy(
+            { 0: 5, 1: 4, 2: 3, length: 3 },
+            {
+                deleteProperty: function (target, property) {
+                    expect().fail();
+                },
+            }
+        );
+        Array.prototype.sort.call(obj);
+    });
+});