[njs] Fixed Array.prototype.sort() according to the specification.

Dmitry Volyntsev xeioex at nginx.com
Mon May 25 14:23:55 UTC 2020


details:   https://hg.nginx.org/njs/rev/1d0825906438
branches:  
changeset: 1397:1d0825906438
user:      Dmitry Volyntsev <xeioex at nginx.com>
date:      Mon May 25 14:21:22 2020 +0000
description:
Fixed Array.prototype.sort() according to the specification.

diffstat:

 src/njs_arr.c            |    4 +-
 src/njs_arr.h            |    8 +-
 src/njs_array.c          |  363 +++++++++++++++++++++++++++++++++-------------
 src/test/njs_unit_test.c |   89 ++++++++++-
 4 files changed, 344 insertions(+), 120 deletions(-)

diffs (565 lines):

diff -r 0287ae53cbb1 -r 1d0825906438 src/njs_arr.c
--- a/src/njs_arr.c	Mon May 11 09:58:28 2020 +0300
+++ b/src/njs_arr.c	Mon May 25 14:21:22 2020 +0000
@@ -111,7 +111,7 @@ njs_arr_add_multiple(njs_arr_t *arr, njs
         old = arr->start;
         arr->start = start;
 
-        memcpy(start, old, (uint32_t) arr->items * arr->item_size);
+        memcpy(start, old, arr->items * arr->item_size);
 
         if (arr->separate == 0) {
             arr->separate = 1;
@@ -121,7 +121,7 @@ njs_arr_add_multiple(njs_arr_t *arr, njs
         }
     }
 
-    item = (char *) arr->start + (uint32_t) arr->items * arr->item_size;
+    item = (char *) arr->start + arr->items * arr->item_size;
 
     arr->items = items;
 
diff -r 0287ae53cbb1 -r 1d0825906438 src/njs_arr.h
--- a/src/njs_arr.h	Mon May 11 09:58:28 2020 +0300
+++ b/src/njs_arr.h	Mon May 25 14:21:22 2020 +0000
@@ -11,11 +11,11 @@
 typedef struct {
     void              *start;
     /*
-     * A array can hold no more than 65536 items.
-     * The item size is no more than 64K.
+     * A array can hold no more than 2**32 items.
+     * the item size is no more than 64K.
      */
-    uint16_t          items;
-    uint16_t          available;
+    uint32_t          items;
+    uint32_t          available;
     uint16_t          item_size;
 
     uint8_t           pointer;
diff -r 0287ae53cbb1 -r 1d0825906438 src/njs_array.c
--- a/src/njs_array.c	Mon May 11 09:58:28 2020 +0300
+++ b/src/njs_array.c	Mon May 25 14:21:22 2020 +0000
@@ -3046,47 +3046,126 @@ unexpected_args:
 }
 
 
-static njs_int_t
-njs_array_string_sort(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs,
-    njs_index_t unused)
+typedef struct {
+    njs_value_t            value;
+    njs_value_t            *str;
+    int64_t                pos;
+} njs_array_sort_slot_t;
+
+
+typedef struct {
+    njs_vm_t               *vm;
+    njs_function_t         *function;
+    njs_bool_t             exception;
+
+    njs_arr_t              strings;
+} njs_array_sort_ctx_t;
+
+
+static int
+njs_array_compare(const void *a, const void *b, void *c)
 {
-    njs_int_t   ret;
-    njs_uint_t  i;
-
-    for (i = 1; i < nargs; i++) {
-        if (!njs_is_string(&args[i])) {
-            ret = njs_value_to_string(vm, &args[i], &args[i]);
-            if (ret != NJS_OK) {
-                return ret;
-            }
+    double                 num;
+    njs_int_t              ret;
+    njs_value_t            arguments[3], retval;
+    njs_array_sort_ctx_t   *ctx;
+    njs_array_sort_slot_t  *aslot, *bslot;
+
+    ctx = c;
+
+    if (ctx->exception) {
+        return 0;
+    }
+
+    aslot = (njs_array_sort_slot_t *) a;
+    bslot = (njs_array_sort_slot_t *) b;
+
+    if (ctx->function != NULL) {
+        njs_set_undefined(&arguments[0]);
+        arguments[1] = aslot->value;
+        arguments[2] = bslot->value;
+
+        ret = njs_function_apply(ctx->vm, ctx->function, arguments, 3, &retval);
+        if (njs_slow_path(ret != NJS_OK)) {
+            goto exception;
+        }
+
+        ret = njs_value_to_number(ctx->vm, &retval, &num);
+        if (njs_slow_path(ret != NJS_OK)) {
+            goto exception;
+        }
+
+        if (njs_slow_path(isnan(num))) {
+            return 0;
+        }
+
+        if (num != 0) {
+            return (num > 0) - (num < 0);
+        }
+
+        goto compare_same;
+    }
+
+    if (aslot->str == NULL) {
+        aslot->str = njs_arr_add(&ctx->strings);
+        ret = njs_value_to_string(ctx->vm, aslot->str, &aslot->value);
+        if (njs_slow_path(ret != NJS_OK)) {
+            goto exception;
         }
     }
 
-    ret = njs_string_cmp(&args[1], &args[2]);
-
-    njs_set_number(&vm->retval, ret);
-
-    return NJS_OK;
+    if (bslot->str == NULL) {
+        bslot->str = njs_arr_add(&ctx->strings);
+        ret = njs_value_to_string(ctx->vm, bslot->str, &bslot->value);
+        if (njs_slow_path(ret != NJS_OK)) {
+            goto exception;
+        }
+    }
+
+    ret = njs_string_cmp(aslot->str, bslot->str);
+
+    if (ret != 0) {
+        return ret;
+    }
+
+compare_same:
+
+    /* Ensures stable sorting. */
+
+    return (aslot->pos > bslot->pos) - (aslot->pos < bslot->pos);
+
+exception:
+
+    ctx->exception = 1;
+
+    return 0;
 }
 
 
-static const njs_function_t  njs_array_string_sort_function = {
-    .object = { .type = NJS_FUNCTION, .shared = 1, .extensible = 1 },
-    .native = 1,
-    .args_offset = 1,
-    .u.native = njs_array_string_sort,
-};
-
-
 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         n, index, length, current;
-    njs_int_t       ret;
-    njs_array_t     *array;
-    njs_value_t     retval, value, *this, *start, arguments[3];
-    njs_function_t  *function;
+    int64_t                i, und, inv, len, nlen, length;
+    njs_int_t              ret;
+    njs_array_t            *array;
+    njs_value_t            *this, *comparefn, *start, *strings, value;
+    njs_array_sort_ctx_t   ctx;
+    njs_array_sort_slot_t  *p, *end, *slots, *nslots;
+
+    comparefn = njs_arg(args, nargs, 1);
+
+    if (njs_is_defined(comparefn)) {
+        if (njs_slow_path(!njs_is_function(comparefn))) {
+            njs_type_error(vm, "comparefn must be callable or undefined");
+            return NJS_ERROR;
+        }
+
+        ctx.function = njs_function(comparefn);
+
+    } else {
+        ctx.function = NULL;
+    }
 
     this = njs_argument(args, 0);
 
@@ -3100,93 +3179,167 @@ njs_array_prototype_sort(njs_vm_t *vm, n
         return ret;
     }
 
-    if (njs_slow_path(length == 0)) {
+    if (njs_slow_path(length < 2)) {
         vm->retval = *this;
         return NJS_OK;
     }
 
-    if (nargs > 1 && njs_is_function(&args[1])) {
-        function = njs_function(&args[1]);
+    ctx.vm = vm;
+    ctx.exception = 0;
+
+    if (njs_fast_path(njs_is_fast_array(this))) {
+        array = njs_array(this);
+        start = array->start;
+
+        /**
+         * Moving undefined and invalid elements to the end.
+         * x x x | undefineds | invalids
+         */
+
+        und = 0;
+        inv = length;
+
+        for (i = length - 1; i >= 0; i--) {
+            if (njs_is_undefined(&start[i])) {
+                value = start[i];
+                start[i] = start[inv - und - 1];
+                start[inv - und - 1] = value;
+                und++;
+                continue;
+            }
+
+            if (!njs_is_valid(&start[i])) {
+                value = start[i];
+                start[i] = start[inv - und - 1];
+                start[inv - und - 1] = njs_value_undefined;
+                start[inv - 1] = njs_value_invalid;
+                inv--;
+                continue;
+            }
+        }
+
+        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;
+        }
 
     } else {
-        function = (njs_function_t *) &njs_array_string_sort_function;
-    }
-
-    if (njs_slow_path(!njs_is_fast_array(this))) {
-        njs_internal_error(vm, "sort() is not implemented yet for objects");
-        return NJS_ERROR;
-    }
-
-    index = 0;
-    current = 0;
-    retval = njs_value_zero;
-    array = njs_array(&args[0]);
-    start = array->start;
-
-start:
-
-    if (njs_is_number(&retval)) {
-
-        /*
-         * The sort function is implemented with the insertion sort algorithm.
-         * Its worst and average computational complexity is O^2.  This point
-         * should be considered as return point from comparison function so
-         * "goto next" moves control to the appropriate step of the algorithm.
-         * The first iteration also goes there because sort->retval is zero.
-         */
-        if (njs_number(&retval) <= 0) {
-            goto next;
+        und = 0;
+        p = NULL;
+        end = NULL;
+        slots = NULL;
+
+        for (i = 0; i < length; i++) {
+            if (p >= end) {
+                nlen = njs_min(njs_max((p - slots) * 2, 8), length);
+                nslots = njs_mp_alloc(vm->mem_pool,
+                                      sizeof(njs_array_sort_slot_t) * nlen);
+                if (njs_slow_path(nslots == NULL)) {
+                    njs_memory_error(vm);
+                    return NJS_ERROR;
+                }
+
+                p = (void *) njs_cpymem(nslots, slots,
+                                   sizeof(njs_array_sort_slot_t) * (p - slots));
+
+                if (slots != NULL) {
+                    njs_mp_free(vm->mem_pool, slots);
+                }
+
+                slots = nslots;
+                end = slots + nlen;
+            }
+
+            ret = njs_value_property_i64(vm, this, i, &p->value);
+            if (njs_slow_path(ret == NJS_ERROR)) {
+                ret = NJS_ERROR;
+                goto exception;
+            }
+
+            if (ret == NJS_DECLINED) {
+                continue;
+            }
+
+            if (njs_is_undefined(&p->value)) {
+                und++;
+                continue;
+            }
+
+            p->pos = i;
+            p->str = NULL;
+            p++;
         }
 
-        n = index;
-
-    swap:
-
-        value = start[n];
-        start[n] = start[n - 1];
-        n--;
-        start[n] = value;
-
-        do {
-            if (n > 0) {
-
-                if (njs_is_valid(&start[n])) {
-
-                    if (njs_is_valid(&start[n - 1])) {
-                        njs_set_undefined(&arguments[0]);
-
-                        /* GC: array elt, array */
-                        arguments[1] = start[n - 1];
-                        arguments[2] = start[n];
-
-                        index = n;
-
-                        ret = njs_function_apply(vm, function, arguments, 3,
-                                                 &retval);
-
-                        if (njs_slow_path(ret != NJS_OK)) {
-                            return ret;
-                        }
-
-                        goto start;
-                    }
-
-                    /* Move invalid values to the end of array. */
-                    goto swap;
+        len = p - slots;
+    }
+
+    strings = njs_arr_init(vm->mem_pool, &ctx.strings, NULL, len + 1,
+                           sizeof(njs_value_t));
+    if (njs_slow_path(strings == NULL)) {
+        ret = NJS_ERROR;
+        goto exception;
+    }
+
+    njs_qsort(slots, len, sizeof(njs_array_sort_slot_t), njs_array_compare,
+              &ctx);
+
+    if (ctx.exception) {
+        ret = NJS_ERROR;
+        goto exception;
+    }
+
+    if (njs_fast_path(njs_is_fast_array(this))) {
+        array = njs_array(this);
+        start = array->start;
+        for (i = 0; i < len; i++) {
+            start[i] = slots[i].value;
+        }
+
+    } else {
+        for (i = 0; i < len; i++) {
+            if (slots[i].pos != i) {
+                ret = njs_value_property_i64_set(vm, this, i, &slots[i].value);
+                if (njs_slow_path(ret == NJS_ERROR)) {
+                    goto exception;
                 }
             }
-
-        next:
-
-            current++;
-            n = current;
-
-        } while (n < array->length);
+        }
+
+        for (i = len; und-- > 0; i++) {
+            ret = njs_value_property_i64_set(vm, this, i,
+                                          njs_value_arg(&njs_value_undefined));
+            if (njs_slow_path(ret == NJS_ERROR)) {
+                goto exception;
+            }
+        }
+
+        for (; i < length; i++) {
+            ret = njs_value_property_i64_delete(vm, this, i, NULL);
+            if (njs_slow_path(ret == NJS_ERROR)) {
+                goto exception;
+            }
+        }
     }
 
-    vm->retval = args[0];
-
-    return NJS_OK;
+    vm->retval = *this;
+
+    ret = NJS_OK;
+
+exception:
+
+    njs_mp_free(vm->mem_pool, slots);
+    njs_arr_destroy(&ctx.strings);
+
+    return ret;
 }
 
 
diff -r 0287ae53cbb1 -r 1d0825906438 src/test/njs_unit_test.c
--- a/src/test/njs_unit_test.c	Mon May 11 09:58:28 2020 +0300
+++ b/src/test/njs_unit_test.c	Mon May 25 14:21:22 2020 +0000
@@ -5979,8 +5979,55 @@ static njs_unit_test_t  njs_test[] =
     { njs_str("var a = ['1','2','3','4','5','6']; a.sort()"),
       njs_str("1,2,3,4,5,6") },
 
+    { njs_str("var a = ['a', 'ab', '', 'aa']; a.sort()"),
+      njs_str(",a,aa,ab") },
+
+    { njs_str("var a = ['a', 'ab', '', 'aa']; a.sort()"),
+      njs_str(",a,aa,ab") },
+
+    { njs_str("var a = [23,1,8,5]; Object.defineProperty(a, '0', {enumerable:false});"
+              "a.sort((x,y)=>x-y)"),
+      njs_str("1,5,8,23") },
+
+    { njs_str("var a = {0:23,1:1,2:8,3:5,length:4};"
+              "Array.prototype.sort.call(a, (x,y)=>x-y);"
+              "Array.prototype.join.call(a)"),
+      njs_str("1,5,8,23") },
+
+    { njs_str("var a = " NJS_LARGE_ARRAY "; "
+              "a[100] = 1; a[512] = -1; a[5] = undefined;"
+              "a.sort();"
+              "a[0] == -1 && a[1] == 1 && a[2] == undefined"),
+      njs_str("true") },
+
+    { njs_str("var a = " NJS_LARGE_ARRAY "; "
+              "a.fill(1, 256, 512); a.fill(undefined, 1000, 1010);"
+              "Object.defineProperty(a, '256', {value: a[256], enumerable:false});"
+              "a.sort();"
+              "a[0] == 1 && a[255] == 1 && Object.getOwnPropertyDescriptor(a, '256').value == undefined"),
+      njs_str("true") },
+
+    { njs_str("var a = [23,1,,undefined,8,,5]; Object.defineProperty(a, '0', {enumerable:false});"
+              "a.sort((x,y)=>x-y)"),
+      njs_str("1,5,8,23,,,") },
+
     { njs_str("var o = { toString: function() { return 5 } };"
-                 "var a = [6,o,4,3,2,1]; a.sort()"),
+              "var a = [6,o,4,3,2,1]; a.sort(undefined)"),
+      njs_str("1,2,3,4,5,6") },
+
+    { njs_str("var a = [undefined,1]; a.sort()"),
+      njs_str("1,") },
+
+    { njs_str("var a = [,1]; a.sort()"),
+      njs_str("1,") },
+
+    { njs_str("var a = [,1,undefined]; a.sort()"),
+      njs_str("1,,") },
+
+    { njs_str("var a = ['1','2','3','4','5','6']; a.sort()"),
+      njs_str("1,2,3,4,5,6") },
+
+    { njs_str("var a = [1,2,3,4,5,6]; a.sort()"),
       njs_str("1,2,3,4,5,6") },
 
     { njs_str("var a = {0:3,1:2,2:1}; Array.prototype.sort.call(a) === a"),
@@ -5990,29 +6037,53 @@ static njs_unit_test_t  njs_test[] =
       njs_str("true") },
 
     { njs_str("var a = [1,2,3,4,5,6];"
-                 "a.sort(function(x, y) { return x - y })"),
+              "a.sort(function(x, y) { return x - y })"),
       njs_str("1,2,3,4,5,6") },
 
-    { njs_str("var a = [6,5,4,3,2,1];"
-                 "a.sort(function(x, y) { return x - y })"),
-      njs_str("1,2,3,4,5,6") },
+    { njs_str("var a = Array(128).fill().map((v,i,a)=>a.length-i);"
+              "a.sort((a,b)=>a-b);"
+              "a.every((v,i,a)=> (i < 1 || v >= a[i-1]))"),
+      njs_str("true") },
 
     { njs_str("var a = [2,2,2,1,1,1];"
-                 "a.sort(function(x, y) { return x - y })"),
+              "a.sort(function(x, y) { return x - y })"),
       njs_str("1,1,1,2,2,2") },
 
     { njs_str("var a = [,,,2,2,2,1,1,1];"
-                 "a.sort(function(x, y) { return x - y })"),
+              "a.sort(function(x, y) { return x - y })"),
       njs_str("1,1,1,2,2,2,,,") },
 
     { njs_str("var a = [,,,,];"
-                 "a.sort(function(x, y) { return x - y })"),
+              "a.sort(function(x, y) { return x - y })"),
       njs_str(",,,") },
 
+    { njs_str("var a = [,,undefined,undefined,,undefined];"
+              "a.sort(function(x, y) { return x - y }); njs.dump(a)"),
+      njs_str("[undefined,undefined,undefined,<empty>,<empty>,<empty>]") },
+
+    { njs_str("var a = [1,,undefined,8,undefined,,undefined,,2];"
+              "a.sort(function(x, y) { return x - y }); njs.dump(a)"),
+      njs_str("[1,2,8,undefined,undefined,undefined,<empty>,<empty>,<empty>]") },
+
     { njs_str("var a = [1,,];"
-                 "a.sort(function(x, y) { return x - y })"),
+              "a.sort(function(x, y) { return x - y })"),
       njs_str("1,") },
 
+    { njs_str("var a = [{ n: 'A', r: 2 },"
+              "         { n: 'B', r: 3 },"
+              "         { n: 'C', r: 2 },"
+              "         { n: 'D', r: 3 },"
+              "         { n: 'E', r: 3 }];"
+              "a.sort((a, b) => b.r - a.r).map(v=>v.n).join('')"),
+      njs_str("BDEAC") },
+
+    { 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") },
+
+    { njs_str("[1,2].sort(1)"),
+      njs_str("TypeError: comparefn must be callable or undefined") },
+
     /* Template literal. */
 
     { njs_str("`"),


More information about the nginx-devel mailing list