LibJS: Implement the SortIndexedProperties AO

Also use it in array_merge_sort() instead of inlining the algorithm.

3 files changed, 56 insertions, 44 deletions

diff --git a/Userland/Libraries/LibJS/Runtime/Array.cpp b/Userland/Libraries/LibJS/Runtime/Array.cpp
index 2de9a8e83d..64c22fe3df 100644
--- a/Userland/Libraries/LibJS/Runtime/Array.cpp
+++ b/Userland/Libraries/LibJS/Runtime/Array.cpp
@@ -8,9 +8,11 @@
 #include <AK/Function.h>
 #include <LibJS/Runtime/AbstractOperations.h>
 #include <LibJS/Runtime/Array.h>
+#include <LibJS/Runtime/ArrayPrototype.h>
 #include <LibJS/Runtime/Completion.h>
 #include <LibJS/Runtime/Error.h>
 #include <LibJS/Runtime/GlobalObject.h>
+#include <LibJS/Runtime/NativeFunction.h>
 
 namespace JS {
 
@@ -199,6 +201,56 @@ ThrowCompletionOr<double> compare_array_elements(GlobalObject& global_object, Va
     return 0;
 }
 
+// 1.1.1.3 SortIndexedProperties ( obj, len, SortCompare, skipHoles ), https://tc39.es/proposal-change-array-by-copy/#sec-sortindexedproperties
+ThrowCompletionOr<MarkedVector<Value>> sort_indexed_properties(GlobalObject& global_object, Object const& object, size_t length, Function<ThrowCompletionOr<double>(Value, Value)> const& sort_compare, bool skip_holes)
+{
+    // 1. Let items be a new empty List.
+    auto items = MarkedVector<Value> { global_object.heap() };
+
+    // 2. Let k be 0.
+    // 3. Repeat, while k < len,
+    for (size_t k = 0; k < length; ++k) {
+        // a. Let Pk be ! ToString(𝔽(k)).
+        auto property_key = PropertyKey { k };
+
+        bool k_read;
+
+        // b. If skipHoles is true, then
+        if (skip_holes) {
+            // i. Let kRead be ? HasProperty(obj, Pk).
+            k_read = TRY(object.has_property(property_key));
+        }
+        // c. Else,
+        else {
+            // i. Let kRead be true.
+            k_read = true;
+        }
+
+        // d. If kRead is true, then
+        if (k_read) {
+            // i. Let kValue be ? Get(obj, Pk).
+            auto k_value = TRY(object.get(property_key));
+
+            // ii. Append kValue to items.
+            items.append(k_value);
+        }
+
+        // e. Set k to k + 1.
+    }
+
+    // 4. Sort items using an implementation-defined sequence of calls to SortCompare. If any such call returns an abrupt completion, stop before performing any further calls to SortCompare or steps in this algorithm and return that Completion Record.
+    // FIXME: Support AK::Function in array_merge_sort() to avoid having to create a NativeFunction.
+    auto* native_comparefn = NativeFunction::create(global_object, "", [&](auto& vm, auto&) -> ThrowCompletionOr<Value> {
+        auto x = vm.argument(0);
+        auto y = vm.argument(1);
+        return TRY(sort_compare(x, y));
+    });
+    TRY(array_merge_sort(global_object, native_comparefn, items));
+
+    // 5. Return items.
+    return items;
+}
+
 // NON-STANDARD: Used to return the value of the ephemeral length property
 ThrowCompletionOr<Optional<PropertyDescriptor>> Array::internal_get_own_property(PropertyKey const& property_key) const
 {
diff --git a/Userland/Libraries/LibJS/Runtime/Array.h b/Userland/Libraries/LibJS/Runtime/Array.h
index a7c158963c..a3d793d05d 100644
--- a/Userland/Libraries/LibJS/Runtime/Array.h
+++ b/Userland/Libraries/LibJS/Runtime/Array.h
@@ -52,5 +52,6 @@ private:
 };
 
 ThrowCompletionOr<double> compare_array_elements(GlobalObject&, Value x, Value y, FunctionObject* comparefn);
+ThrowCompletionOr<MarkedVector<Value>> sort_indexed_properties(GlobalObject&, Object const&, size_t length, Function<ThrowCompletionOr<double>(Value, Value)> const& sort_compare, bool skip_holes);
 
 }
diff --git a/Userland/Libraries/LibJS/Runtime/ArrayPrototype.cpp b/Userland/Libraries/LibJS/Runtime/ArrayPrototype.cpp
index e7d9cfa72d..f067239c02 100644
--- a/Userland/Libraries/LibJS/Runtime/ArrayPrototype.cpp
+++ b/Userland/Libraries/LibJS/Runtime/ArrayPrototype.cpp
@@ -901,54 +901,13 @@ ThrowCompletionOr<void> array_merge_sort(GlobalObject& global_object, FunctionOb
         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 = TRY(call(global_object, *compare_func, js_undefined(), left[left_index], right[right_index]));
-            auto number = TRY(call_result.to_number(global_object));
-            if (number.is_nan())
-                comparison_result = 0;
-            else
-                comparison_result = number.as_double();
-        } 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 = TRY(x.to_primitive_string(global_object));
-
-            auto y_string = TRY(y.to_primitive_string(global_object));
-
-            auto x_string_value = Value(x_string);
-            auto y_string_value = Value(y_string);
-
-            // Because they are called with primitive strings, these is_less_than calls
-            // should never result in a VM exception.
-            auto x_lt_y_relation = MUST(is_less_than(global_object, true, x_string_value, y_string_value));
-            VERIFY(x_lt_y_relation != TriState::Unknown);
-            auto y_lt_x_relation = MUST(is_less_than(global_object, true, y_string_value, x_string_value));
-            VERIFY(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;
-            }
-        }
+        double comparison_result = TRY(compare_array_elements(global_object, x, y, compare_func));
 
         if (comparison_result <= 0) {
-            arr_to_sort.append(left[left_index]);
+            arr_to_sort.append(x);
             left_index++;
         } else {
-            arr_to_sort.append(right[right_index]);
+            arr_to_sort.append(y);
             right_index++;
         }
     }