[njs] Ensuring Array.prototype.sort() stability.

[Dmitry Volyntsev]

details:   https://hg.nginx.org/njs/rev/c2fa0f18e58d
branches:  
changeset: 1418:c2fa0f18e58d
user:      Dmitry Volyntsev <xeioex at nginx.com>
date:      Tue Jun 02 12:08:04 2020 +0000
description:
Ensuring Array.prototype.sort() stability.

For fast arrays with empty or undefined elements.

This closes #312 issue on Github.

diffstat:

 src/njs_array.c          |  69 ++++++++++++++++++++++++-----------------------
 src/test/njs_unit_test.c |   6 ++++
 2 files changed, 41 insertions(+), 34 deletions(-)

diffs (128 lines):

diff -r 1ce9a0895630 -r c2fa0f18e58d src/njs_array.c
--- a/src/njs_array.c	Tue Jun 02 14:59:30 2020 +0000
+++ b/src/njs_array.c	Tue Jun 02 12:08:04 2020 +0000
@@ -3216,8 +3216,8 @@ static njs_int_t
 njs_array_prototype_sort(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs,
     njs_index_t unused)
 {
-    int64_t                i, und, inv, len, nlen, length;
-    njs_int_t              ret;
+    int64_t                i, und, len, nlen, length;
+    njs_int_t              ret, fast_path;
     njs_array_t            *array;
     njs_value_t            *this, *comparefn, *start, *strings;
     njs_array_sort_ctx_t   ctx;
@@ -3260,50 +3260,46 @@ njs_array_prototype_sort(njs_vm_t *vm, n
     ctx.strings.pointer = 0;
     ctx.exception = 0;
 
-    if (njs_fast_path(njs_is_fast_array(this))) {
+    fast_path = njs_is_fast_array(this);
+
+    if (njs_fast_path(fast_path)) {
         array = njs_array(this);
         start = array->start;
 
-        /**
-         * Moving undefined and invalid elements to the end.
-         * x x x | undefineds | invalids
-         */
+        slots = njs_mp_alloc(vm->mem_pool,
+                             sizeof(njs_array_sort_slot_t) * length);
+        if (njs_slow_path(slots == NULL)) {
+                return NJS_ERROR;
+        }
 
         und = 0;
-        inv = length;
-
-        for (i = length - 1; i >= 0; i--) {
-            if (njs_is_undefined(&start[i])) {
-                start[i] = start[inv - und - 1];
-                start[inv - und - 1] = njs_value_undefined;
+        p = slots;
+
+        for (i = 0; i < length; i++) {
+            if (njs_slow_path(!njs_is_valid(&start[i]))) {
+                fast_path = 0;
+                njs_mp_free(vm->mem_pool, slots);
+                slots = NULL;
+                goto slow_path;
+            }
+
+            if (njs_slow_path(njs_is_undefined(&start[i]))) {
                 und++;
                 continue;
             }
 
-            if (!njs_is_valid(&start[i])) {
-                start[i] = start[inv - und - 1];
-                start[inv - und - 1] = njs_value_undefined;
-                start[inv - 1] = njs_value_invalid;
-                inv--;
-                continue;
-            }
+            p->value = start[i];
+            p->pos = i;
+            p->str = NULL;
+            p++;
         }
 
-        len = inv - und;
-
-        slots = njs_mp_alloc(vm->mem_pool,
-                             sizeof(njs_array_sort_slot_t) * len);
-        if (njs_slow_path(slots == NULL)) {
-                return NJS_ERROR;
-        }
-
-        for (i = 0; i < len; i++) {
-            slots[i].value = start[i];
-            slots[i].pos = i;
-            slots[i].str = NULL;
-        }
+        len = p - slots;
 
     } else {
+
+slow_path:
+
         und = 0;
         p = NULL;
         end = NULL;
@@ -3369,13 +3365,18 @@ njs_array_prototype_sort(njs_vm_t *vm, n
         goto exception;
     }
 
-    if (njs_fast_path(njs_is_fast_array(this))) {
+    if (njs_fast_path(fast_path)) {
         array = njs_array(this);
         start = array->start;
+
         for (i = 0; i < len; i++) {
             start[i] = slots[i].value;
         }
 
+        for (i = len; und-- > 0; i++) {
+            start[i] = njs_value_undefined;
+        }
+
     } else {
         for (i = 0; i < len; i++) {
             if (slots[i].pos != i) {
diff -r 1ce9a0895630 -r c2fa0f18e58d src/test/njs_unit_test.c
--- a/src/test/njs_unit_test.c	Tue Jun 02 14:59:30 2020 +0000
+++ b/src/test/njs_unit_test.c	Tue Jun 02 12:08:04 2020 +0000
@@ -6104,6 +6104,12 @@ static njs_unit_test_t  njs_test[] =
     { njs_str("[1,2,3].sort(()=>-1)"),
       njs_str("3,2,1") },
 
+    { njs_str("njs.dump([undefined,1,2,3].sort(()=>0))"),
+      njs_str("[1,2,3,undefined]") },
+
+    { njs_str("njs.dump([1,,2,3].sort(()=>0))"),
+      njs_str("[1,2,3,<empty>]") },
+
     { njs_str("var count = 0;"
               "[4,3,2,1].sort(function(x, y) { if (count++ == 2) {throw Error('Oops'); }; return x - y })"),
       njs_str("Error: Oops") },