Fix sorting bug when using BSP tree index + add autotest.

We use stable sorting to keep insertion order. This works fine as long
as we sort a complete list of siblings in one go, and this list already
has items in insertion order. But if we shuffle such a list, the only
way to get proper sort order again (with insertion order intact), is
if each item has a sibling index. We used to have this, but we don't
have it anymore (as it's not needed for NoIndex mode).

So until we separate the BSP index into a separate class and add this
index there, we add this workaround which uses the toplevelitems list
to ensure the items have the correct order.

Reviewed-by: bnilsen

2 files changed, 36 insertions, 18 deletions

diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index db16213..f50d210 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -6190,10 +6190,8 @@ void QGraphicsItem::addToIndex()
         // ### add to child index only if applicable
         return;
     }
-    if (d_ptr->scene) {
+    if (d_ptr->scene)
         d_ptr->scene->d_func()->addToIndex(this);
-        d_ptr->scene->d_func()->markDirty(this);
-    }
 }
 
 /*!
@@ -6209,10 +6207,8 @@ void QGraphicsItem::removeFromIndex()
         // ### remove from child index only if applicable
         return;
     }
-    if (d_ptr->scene) {
-        d_ptr->scene->d_func()->markDirty(this);
+    if (d_ptr->scene)
         d_ptr->scene->d_func()->removeFromIndex(this);
-    }
 }
 
 /*!
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index b63efd6..e6c3503 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -5112,18 +5112,42 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     } else if (indexMethod == QGraphicsScene::NoIndex || !exposedRegion) {
         children = &this->topLevelItems;
     } else {
-        tmp = estimateItemsInRect(viewTransform.inverted().mapRect(exposedRegion->boundingRect()));
+        QRectF sceneRect = viewTransform.inverted().mapRect(QRectF(exposedRegion->boundingRect().adjusted(-1, -1, 1, 1)));
+        if (!largestUntransformableItem.isEmpty()) {
+            // ### Nuke this when we move the indexing code into a separate
+            // class.  All the largestUntransformableItem code should then go
+            // away, and the estimate function should return untransformable
+            // items as well.
+            QRectF untr = largestUntransformableItem;
+            QRectF ltri = viewTransform.inverted().mapRect(untr);
+            ltri.adjust(-untr.width(), -untr.height(), untr.width(), untr.height());
+            sceneRect.adjust(-ltri.width(), -ltri.height(), ltri.width(), ltri.height());
+        }
+        tmp = estimateItemsInRect(sceneRect);
 
         QList<QGraphicsItem *> tli;
-        for (int i = 0; i < tmp.size(); ++i) {
-            QGraphicsItem *it = tmp.at(i)->topLevelItem();
-            if (!it->d_ptr->itemDiscovered) {
-                tli << it;
-                it->d_ptr->itemDiscovered = 1;
+        for (int i = 0; i < tmp.size(); ++i)
+            tmp.at(i)->topLevelItem()->d_ptr->itemDiscovered = 1;
+
+        // Sort if the toplevel list is unsorted.
+        if (needSortTopLevelItems) {
+            needSortTopLevelItems = false;
+            qStableSort(this->topLevelItems.begin(),
+                        this->topLevelItems.end(), qt_notclosestLeaf);
+        }
+
+        for (int i = 0; i < this->topLevelItems.size(); ++i) {
+            // ### Investigate smarter ways. Looping through all top level
+            // items is not optimal. If the BSP tree is to have maximum
+            // effect, it should be possible to sort the subset of items
+            // quickly. We must use this approach for now, as it's the only
+            // current way to keep the stable sorting order (insertion order).
+            QGraphicsItem *item = this->topLevelItems.at(i);
+            if (item->d_ptr->itemDiscovered) {
+                item->d_ptr->itemDiscovered = 0;
+                tli << item;
             }
         }
-        for (int i = 0; i < tli.size(); ++i)
-            tli.at(i)->d_ptr->itemDiscovered = 0;
 
         tmp = tli;
         children = &tmp;
@@ -5147,9 +5171,7 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
         if (item && item->d_ptr->needSortChildren) {
             item->d_ptr->needSortChildren = 0;
             qStableSort(children->begin(), children->end(), qt_notclosestLeaf);
-        } else if (!item && children == &tmp) {
-            qStableSort(children->begin(), children->end(), qt_notclosestLeaf);
-        } else if (!item && needSortTopLevelItems) {
+        } else if (!item && needSortTopLevelItems && children != &tmp) {
             needSortTopLevelItems = false;
             qStableSort(children->begin(), children->end(), qt_notclosestLeaf);
         }
@@ -5220,7 +5242,7 @@ void QGraphicsScenePrivate::markDirty(QGraphicsItem *item, const QRectF &rect, b
 
     if (item->d_ptr->discardUpdateRequest(/*ignoreClipping=*/maybeDirtyClipPath,
                                           /*ignoreVisibleBit=*/force,
-                                          /*ignoreDirtyBit=*/removingItemFromScene,
+                                          /*ignoreDirtyBit=*/removingItemFromScene || invalidateChildren,
                                           /*ignoreOpacity=*/ignoreOpacity)) {
         return;
     }