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

3 files changed, 92 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;
     }
diff --git a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
index af34fe5..481dc6b 100644
--- a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
+++ b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
@@ -226,6 +226,8 @@ private slots:
     void itemUsesExtendedStyleOption();
     void itemSendsGeometryChanges();
     void moveItem();
+    void sorting_data();
+    void sorting();
 
     // task specific tests below me
     void task141694_textItemEnsureVisible();
@@ -6926,5 +6928,59 @@ void tst_QGraphicsItem::moveItem()
     QCOMPARE(view.paintedRegion, expectedParentRegion);
 }
 
+void tst_QGraphicsItem::sorting_data()
+{
+    QTest::addColumn<int>("index");
+
+    QTest::newRow("NoIndex") << int(QGraphicsScene::NoIndex);
+    QTest::newRow("BspTreeIndex") << int(QGraphicsScene::BspTreeIndex);
+}
+
+void tst_QGraphicsItem::sorting()
+{
+    _paintedItems.clear();
+
+    QGraphicsScene scene;
+    QGraphicsItem *grid[100][100];
+    for (int x = 0; x < 100; ++x) {
+        for (int y = 0; y < 100; ++y) {
+            PainterItem *item = new PainterItem;
+            item->setPos(x * 25, y * 25);
+            item->setData(0, QString("%1x%2").arg(x).arg(y));
+            grid[x][y] = item;
+            scene.addItem(item);
+        }
+    }
+
+    PainterItem *item1 = new PainterItem;
+    PainterItem *item2 = new PainterItem;
+    item1->setData(0, "item1");
+    item2->setData(0, "item2");
+    scene.addItem(item1);
+    scene.addItem(item2);
+
+    QGraphicsView view(&scene);
+    view.setResizeAnchor(QGraphicsView::NoAnchor);
+    view.setTransformationAnchor(QGraphicsView::NoAnchor);
+    view.resize(100, 100);
+    view.setFrameStyle(0);
+    view.show();
+#ifdef Q_WS_X11
+    qt_x11_wait_for_window_manager(&view);
+#endif
+    QTest::qWait(100);
+
+    _paintedItems.clear();
+
+    view.viewport()->repaint();
+
+    QCOMPARE(_paintedItems, QList<QGraphicsItem *>()
+                 << grid[0][0] << grid[0][1] << grid[0][2] << grid[0][3]
+                 << grid[1][0] << grid[1][1] << grid[1][2] << grid[1][3]
+                 << grid[2][0] << grid[2][1] << grid[2][2] << grid[2][3]
+                 << grid[3][0] << grid[3][1] << grid[3][2] << grid[3][3]
+                 << item1 << item2);
+}
+
 QTEST_MAIN(tst_QGraphicsItem)
 #include "tst_qgraphicsitem.moc"