[njs] Fixed arrays expansion.

[Valentin Bartenev]

details:   https://hg.nginx.org/njs/rev/8fe38b9f8a94
branches:  
changeset: 960:8fe38b9f8a94
user:      Valentin Bartenev <vbart at nginx.com>
date:      Wed May 08 19:09:10 2019 +0300
description:
Fixed arrays expansion.

There were two problems with njs_array_expand():

 1. It checked that the requred size with the appended elements wasn't bigger
    then the array size and then did nothing.  If there were elements removed
    from the beggining (by shift() operation), then "size <= array->size" can
    be true even if there wasn't enought free space after the array.

 2. After allocating more space to prepend elements, it set array->size without
    counting those elements.

Probably, the original idea was to decrement array->size while removing
elements from the beginning, but it wasn't done right.  Even if so, the
new version of the function looks cleaner.

This closes #152 and closes #153 issues on Github.

diffstat:

 njs/njs_array.c          |  22 ++++++++++++----------
 njs/test/njs_unit_test.c |   3 +++
 2 files changed, 15 insertions(+), 10 deletions(-)

diffs (69 lines):

diff -r cb9cbb358a8b -r 8fe38b9f8a94 njs/njs_array.c
--- a/njs/njs_array.c	Wed May 08 19:09:10 2019 +0300
+++ b/njs/njs_array.c	Wed May 08 19:09:10 2019 +0300
@@ -214,15 +214,19 @@ njs_ret_t
 njs_array_expand(njs_vm_t *vm, njs_array_t *array, uint32_t prepend,
     uint32_t append)
 {
+    uint32_t     free_before, free_after;
     uint64_t     size;
     njs_value_t  *start, *old;
 
-    size = (uint64_t) append + array->length;
-
-    if (nxt_fast_path(size <= array->size && prepend == 0)) {
+    free_before = array->start - array->data;
+    free_after = array->size - array->length - free_before;
+
+    if (nxt_fast_path(free_before >= prepend && free_after >= append)) {
         return NXT_OK;
     }
 
+    size = (uint64_t) prepend + array->length + append;
+
     if (size < 16) {
         size *= 2;
 
@@ -230,12 +234,12 @@ njs_array_expand(njs_vm_t *vm, njs_array
         size += size / 2;
     }
 
-    if (nxt_slow_path((prepend + size) > NJS_ARRAY_MAX_LENGTH)) {
+    if (nxt_slow_path(size > NJS_ARRAY_MAX_LENGTH)) {
         goto memory_error;
     }
 
     start = nxt_mp_align(vm->mem_pool, sizeof(njs_value_t),
-                         (prepend + size) * sizeof(njs_value_t));
+                         size * sizeof(njs_value_t));
     if (nxt_slow_path(start == NULL)) {
         goto memory_error;
     }
@@ -728,11 +732,9 @@ njs_array_prototype_unshift(njs_vm_t *vm
         n = nargs - 1;
 
         if (n != 0) {
-            if ((intptr_t) n > (array->start - array->data)) {
-                ret = njs_array_expand(vm, array, n, 0);
-                if (nxt_slow_path(ret != NXT_OK)) {
-                    return ret;
-                }
+            ret = njs_array_expand(vm, array, n, 0);
+            if (nxt_slow_path(ret != NXT_OK)) {
+                return ret;
             }
 
             array->length += n;
diff -r cb9cbb358a8b -r 8fe38b9f8a94 njs/test/njs_unit_test.c
--- a/njs/test/njs_unit_test.c	Wed May 08 19:09:10 2019 +0300
+++ b/njs/test/njs_unit_test.c	Wed May 08 19:09:10 2019 +0300
@@ -3730,6 +3730,9 @@ static njs_unit_test_t  njs_test[] =
                  "len +' '+ a +' '+ a.shift()"),
       nxt_string("5 3,4,5,1,2 3") },
 
+    { nxt_string("var a=[0], n = 64; while(--n) {a.push(n); a.shift()}; a"),
+      nxt_string("1") },
+
     { nxt_string("var a = []; a.splice()"),
       nxt_string("") },