details: https://hg.nginx.org/njs/rev/c2fa0f18e58d
branches:
changeset: 1418:c2fa0f18e58d
user: Dmitry Volyntsev <xeioex@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") },
_______________________________________________
nginx-devel mailing list
nginx-devel@nginx.org
http://mailman.nginx.org/mailman/listinfo/nginx-devel