Fixes to sparse array handling

deleting entries in sparse arrays could lead
to rather unexpected results where values got
moved to wrong indices, as we didn't correctly
update the size_left values in the red-black tree.

Change-Id: If71fcc04d39f257194394cb4f734d0db14b92b69
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>

3 files changed, 64 insertions, 41 deletions

diff --git a/src/qml/jsruntime/qv4sparsearray.cpp b/src/qml/jsruntime/qv4sparsearray.cpp
index 3ee89d5b53..97dd695067 100644
--- a/src/qml/jsruntime/qv4sparsearray.cpp
+++ b/src/qml/jsruntime/qv4sparsearray.cpp
@@ -245,51 +245,51 @@ void SparseArray::deleteNode(SparseArrayNode *z)
             else
                 mostLeftNode = y->parent();
         }
-    } else {
-        if (y->right == 0) {
+    } else if (y->right == 0) {
             x = y->left;
-        } else {
-            y = y->right;
-            while (y->left != 0)
-                y = y->left;
-            x = y->right;
-        }
+    } else {
+        y = y->right;
+        while (y->left != 0)
+            y = y->left;
+        x = y->right;
     }
     if (y != z) {
-        z->left->setParent(y);
-        y->left = z->left;
+        // move y into the position of z
+        // adjust size_left so the keys are ok.
+        z->size_left += y->size_left;
+        SparseArrayNode *n = y->parent();
+        while (n != z) {
+            n->size_left -= y->size_left;
+            n = n->parent();
+        }
+        y->size_left = 0;
+        z->value = y->value;
+
         if (y != z->right) {
             x_parent = y->parent();
-            if (x)
-                x->setParent(y->parent());
             y->parent()->left = x;
-            y->right = z->right;
-            z->right->setParent(y);
         } else {
-            x_parent = y;
+            x_parent = z;
+            z->right = x;
         }
-        if (root == z)
-            root = y;
-        else if (z->parent()->left == z)
-            z->parent()->left = y;
-        else
-            z->parent()->right = y;
-        y->setParent(z->parent());
-        // Swap the colors
-        SparseArrayNode::Color c = y->color();
-        y->setColor(z->color());
-        z->setColor(c);
-        y = z;
+        if (x)
+            x->setParent(x_parent);
     } else {
         x_parent = y->parent();
         if (x)
             x->setParent(y->parent());
-        if (root == z)
+        if (root == y)
             root = x;
-        else if (z->parent()->left == z)
-            z->parent()->left = x;
-        else
-            z->parent()->right = x;
+        else if (y->parent()->left == y) {
+            y->parent()->left = x;
+            if (x)
+                x->size_left += y->size_left;
+        } else {
+            y->parent()->right = x;
+            if (x)
+                x->size_left += y->size_left;
+        }
+        y->size_left = 0;
     }
     if (y->color() != SparseArrayNode::Red) {
         while (x != root && (x == 0 || x->color() == SparseArrayNode::Black)) {
diff --git a/src/qml/jsruntime/qv4sparsearray_p.h b/src/qml/jsruntime/qv4sparsearray_p.h
index 4746498963..f2ad167a17 100644
--- a/src/qml/jsruntime/qv4sparsearray_p.h
+++ b/src/qml/jsruntime/qv4sparsearray_p.h
@@ -49,6 +49,7 @@
 #include "qv4property_p.h"
 #include <assert.h>
 
+//#define Q_MAP_DEBUG
 #ifdef Q_MAP_DEBUG
 #include <QtCore/qdebug.h>
 #endif
@@ -182,6 +183,8 @@ public:
 
     SparseArrayNode *findNode(uint akey) const;
 
+    uint nEntries() const { return numEntries; }
+
     uint pop_front();
     void push_front(uint at);
     uint pop_back(uint len);
@@ -208,7 +211,7 @@ public:
     typedef qptrdiff difference_type;
     typedef int size_type;
 
-#ifdef Q_MAP_DEBUG
+#ifndef QT_NO_DEBUG
     void dump() const;
 #endif
 };
@@ -281,23 +284,22 @@ inline void SparseArray::push_back(uint index, uint len)
     n->value = index;
 }
 
-#ifdef Q_MAP_DEBUG
-
-void SparseArray::dump() const
+#ifndef QT_NO_DEBUG
+inline void SparseArray::dump() const
 {
-    const_iterator it = begin();
+    const SparseArrayNode *it = begin();
     qDebug() << "map dump:";
     while (it != end()) {
-        const SparseArrayNode *n = it.i;
+        const SparseArrayNode *n = it;
         int depth = 0;
         while (n && n != root()) {
             ++depth;
             n = n->parent();
         }
         QByteArray space(4*depth, ' ');
-        qDebug() << space << (it.i->color() == SparseArrayNode::Red ? "Red  " : "Black") << it.i << it.i->left << it.i->right
-                 << it.key() << it.value();
-        ++it;
+        qDebug() << space << (it->color() == SparseArrayNode::Red ? "Red  " : "Black") << it << it->size_left << it->left << it->right
+                 << it->key() << it->value;
+        it = it->nextNode();
     }
     qDebug() << "---------";
 }
diff --git a/tests/manual/v4/sparsearraytest.js b/tests/manual/v4/sparsearraytest.js
new file mode 100644
index 0000000000..921a750472
--- /dev/null
+++ b/tests/manual/v4/sparsearraytest.js
@@ -0,0 +1,21 @@
+var max
+for (max = 2; max < 100; ++max) {
+    var arr = [];
+    arr[10000000] = -1
+    var i;
+    var j;
+    for (i = 0; i < max; ++i)
+        arr[i] = i;
+    for (i = 1; i < max; i += 2) {
+        delete arr[i];
+        for (j = 0; j < max; ++j) {
+            if (j <= i && (j %2)) {
+                if (arr[j] != undefined)
+                    throw "err1"
+            } else {
+                if (arr[j] != j)
+                    throw "err2"
+            }
+        }
+    }
+}