Refactor QGraphicsScene::drawSubtreeRecursive.

It's easier to read and maintain the code now. This version is also
faster than the old one and makes it easier to implement another
cut-off I'm working on.

All auto-tests still pass. Examples/demos run fine.

3 files changed, 169 insertions, 153 deletions

diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 4d4c3b4..6c97886 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -1424,6 +1424,63 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item)
     return 0;
 }
 
+QList<QGraphicsItem *> QGraphicsScenePrivate::topLevelItemsInStackingOrder(const QTransform *const viewTransform,
+                                                                           QRegion *exposedRegion)
+{
+    if (indexMethod == QGraphicsScene::NoIndex || !exposedRegion) {
+        if (needSortTopLevelItems) {
+            needSortTopLevelItems = false;
+            qStableSort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf);
+        }
+        return topLevelItems;
+    }
+
+    const QRectF exposedRect = exposedRegion->boundingRect().adjusted(-1, -1, 1, 1);
+    QRectF sceneRect;
+    QTransform invertedViewTransform(Qt::Uninitialized);
+    if (!viewTransform) {
+        sceneRect = exposedRect;
+    } else {
+        invertedViewTransform = viewTransform->inverted();
+        sceneRect = invertedViewTransform.mapRect(exposedRect);
+    }
+    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 ? untr : invertedViewTransform.mapRect(untr);
+        ltri.adjust(-untr.width(), -untr.height(), untr.width(), untr.height());
+        sceneRect.adjust(-ltri.width(), -ltri.height(), ltri.width(), ltri.height());
+    }
+
+    QList<QGraphicsItem *> tmp = estimateItemsInRect(sceneRect);
+    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(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf);
+    }
+
+    QList<QGraphicsItem *> tli;
+    for (int i = 0; i < 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 = topLevelItems.at(i);
+        if (item->d_ptr->itemDiscovered) {
+            item->d_ptr->itemDiscovered = 0;
+            tli << item;
+        }
+    }
+    return tli;
+}
+
 void QGraphicsScenePrivate::recursive_items_helper(QGraphicsItem *item, QRectF rect,
                                                    QList<QGraphicsItem *> *items,
                                                    const QTransform &parentTransform,
@@ -5045,165 +5102,118 @@ void QGraphicsScenePrivate::drawItemHelper(QGraphicsItem *item, QPainter *painte
 }
 
 void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter,
-                                                 const QTransform &viewTransform,
+                                                 const QTransform *const viewTransform,
                                                  QRegion *exposedRegion, QWidget *widget,
-                                                 QList<QGraphicsItem *> *topLevelItems,
                                                  qreal parentOpacity)
 {
-    // Calculate opacity.
-    qreal opacity;
-    bool invisibleButChildIgnoresParentOpacity = false;
-    if (item) {
-        if (!item->d_ptr->visible)
-            return;
-        opacity = item->d_ptr->combineOpacityFromParent(parentOpacity);
-        if (opacity == 0.0 && !(item->d_ptr->flags & QGraphicsItem::ItemDoesntPropagateOpacityToChildren)) {
-            invisibleButChildIgnoresParentOpacity = !item->d_ptr->childrenCombineOpacity();
-            if (!invisibleButChildIgnoresParentOpacity)
-                return;
-        }
-    } else {
-        opacity = parentOpacity;
-    }
-
-    // Item is invisible.
-    bool hasContents = item && !(item->d_ptr->flags & QGraphicsItem::ItemHasNoContents);
-    bool invisible = !hasContents || invisibleButChildIgnoresParentOpacity;
-
-    // Calculate the full transform for this item.
-    bool wasDirtyParentSceneTransform = false;
-    bool dontDrawItem = true;
-    QTransform transform(Qt::Uninitialized);
-    if (item) {
-        if (item->d_ptr->itemIsUntransformable()) {
-            transform = item->deviceTransform(viewTransform);
-        } else {
-            if (item->d_ptr->dirtySceneTransform) {
-                item->d_ptr->sceneTransform = item->d_ptr->parent ? item->d_ptr->parent->d_ptr->sceneTransform
-                                              : QTransform();
-                item->d_ptr->combineTransformFromParent(&item->d_ptr->sceneTransform);
-                item->d_ptr->dirtySceneTransform = 0;
-                wasDirtyParentSceneTransform = true;
-            }
-            transform = item->d_ptr->sceneTransform;
-            transform *= viewTransform;
-        }
-
-        if (!invisible) {
-            QRectF brect = item->boundingRect();
-            // ### This does not take the clip into account.
-            _q_adjustRect(&brect);
-            QRect viewBoundingRect = transform.mapRect(brect).toRect();
-            item->d_ptr->paintedViewBoundingRects.insert(widget, viewBoundingRect);
-            viewBoundingRect.adjust(-1, -1, 1, 1);
-            if (exposedRegion)
-                dontDrawItem = !exposedRegion->intersects(viewBoundingRect);
-            else
-                dontDrawItem = viewBoundingRect.isEmpty();
-        }
-    }
+    Q_ASSERT(item);
 
-    // Find and sort children.
-    QList<QGraphicsItem *> tmp;
-    QList<QGraphicsItem *> *children = 0;
-    if (item) {
-        children = &item->d_ptr->children;
-    } else if (topLevelItems) {
-        children = topLevelItems;
-    } else if (indexMethod == QGraphicsScene::NoIndex || !exposedRegion) {
-        children = &this->topLevelItems;
-    } else {
-        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);
+    if (!item->d_ptr->visible)
+        return;
 
-        QList<QGraphicsItem *> tli;
-        for (int i = 0; i < tmp.size(); ++i)
-            tmp.at(i)->topLevelItem()->d_ptr->itemDiscovered = 1;
+    const bool itemHasContents = !(item->d_ptr->flags & QGraphicsItem::ItemHasNoContents);
+    const bool itemHasChildren = !item->d_ptr->children.isEmpty();
+    if (!itemHasContents && !itemHasChildren)
+        return; // Item has neither contents nor children!(?)
 
-        // Sort if the toplevel list is unsorted.
-        if (needSortTopLevelItems) {
-            needSortTopLevelItems = false;
-            qStableSort(this->topLevelItems.begin(),
-                        this->topLevelItems.end(), qt_notclosestLeaf);
-        }
+    const qreal opacity = item->d_ptr->combineOpacityFromParent(parentOpacity);
+    const bool itemIsFullyTransparent = (opacity < 0.0001);
+    if (itemIsFullyTransparent && (!itemHasChildren || item->d_ptr->childrenCombineOpacity()))
+        return;
 
-        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;
+    QTransform transform(Qt::Uninitialized);
+    QTransform *transformPtr = 0;
+#define ENSURE_TRANSFORM_PTR \
+    if (!transformPtr) { \
+        Q_ASSERT(!itemIsUntransformable); \
+        if (viewTransform) { \
+            transform = item->d_ptr->sceneTransform; \
+            transform *= *viewTransform; \
+            transformPtr = &transform; \
+        } else { \
+            transformPtr = &item->d_ptr->sceneTransform; \
+        } \
+    }
+
+    // Update the item's scene transform if the item is transformable;
+    // otherwise calculate the full transform,
+    bool wasDirtyParentSceneTransform = false;
+    const bool itemIsUntransformable = item->d_ptr->itemIsUntransformable();
+    if (itemIsUntransformable) {
+        transform = item->deviceTransform(viewTransform ? *viewTransform : QTransform());
+        transformPtr = &transform;
+    } else if (item->d_ptr->dirtySceneTransform) {
+        item->d_ptr->sceneTransform = item->d_ptr->parent ? item->d_ptr->parent->d_ptr->sceneTransform
+                                                          : QTransform();
+        item->d_ptr->combineTransformFromParent(&item->d_ptr->sceneTransform);
+        item->d_ptr->dirtySceneTransform = 0;
+        wasDirtyParentSceneTransform = true;
+    }
+
+    const bool itemClipsChildrenToShape = (item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape);
+    bool drawItem = itemHasContents && !itemIsFullyTransparent;
+    if (drawItem) {
+        const QRectF brect = adjustedItemBoundingRect(item);
+        ENSURE_TRANSFORM_PTR
+        QRect viewBoundingRect = transformPtr->mapRect(brect).toRect();
+        item->d_ptr->paintedViewBoundingRects.insert(widget, viewBoundingRect);
+        viewBoundingRect.adjust(-1, -1, 1, 1);
+        drawItem = exposedRegion ? exposedRegion->intersects(viewBoundingRect) : !viewBoundingRect.isEmpty();
+        if (!drawItem) {
+            if (!itemHasChildren)
+                return;
+            if (itemClipsChildrenToShape) {
+                if (wasDirtyParentSceneTransform)
+                    item->d_ptr->invalidateChildrenSceneTransform();
+                return;
             }
         }
+    } // else we know for sure this item has children we must process.
 
-        tmp = tli;
-        children = &tmp;
-    }
-
-    bool childClip = (item && (item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape));
-    bool dontDrawChildren = item && hasContents && dontDrawItem && childClip;
-    childClip &= !dontDrawChildren && !children->isEmpty();
-    if (item && invisible)
-        dontDrawItem = true;
-
-    // Clip children.
-    if (childClip) {
-        painter->save();
-        painter->setWorldTransform(transform);
-        painter->setClipPath(item->shape(), Qt::IntersectClip);
-    }
-    
-    if (!dontDrawChildren) {
-        if (item && item->d_ptr->needSortChildren) {
+    int i = 0;
+    if (itemHasChildren) {
+        if (item->d_ptr->needSortChildren) {
             item->d_ptr->needSortChildren = 0;
-            qStableSort(children->begin(), children->end(), qt_notclosestLeaf);
-        } else if (!item && needSortTopLevelItems && children != &tmp) {
-            needSortTopLevelItems = false;
-            qStableSort(children->begin(), children->end(), qt_notclosestLeaf);
+            qStableSort(item->d_ptr->children.begin(), item->d_ptr->children.end(), qt_notclosestLeaf);
         }
-    }
 
-    // Draw children behind
-    int i = 0;
-    if (!dontDrawChildren) {
-        // ### Don't visit children that don't ignore parent opacity if this
-        // item is invisible.
-        for (i = 0; i < children->size(); ++i) {
-            QGraphicsItem *child = children->at(i);
+        if (itemClipsChildrenToShape) {
+            painter->save();
+            ENSURE_TRANSFORM_PTR
+            painter->setWorldTransform(*transformPtr);
+            painter->setClipPath(item->shape(), Qt::IntersectClip);
+        }
+
+        // Draw children behind
+        for (i = 0; i < item->d_ptr->children.size(); ++i) {
+            QGraphicsItem *child = item->d_ptr->children.at(i);
             if (wasDirtyParentSceneTransform)
                 child->d_ptr->dirtySceneTransform = 1;
             if (!(child->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent))
                 break;
-            drawSubtreeRecursive(child, painter, viewTransform, exposedRegion, widget,
-                                 0, opacity);
+            if (itemIsFullyTransparent && !(child->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity))
+                continue;
+            drawSubtreeRecursive(child, painter, viewTransform, exposedRegion, widget, opacity);
         }
     }
 
     // Draw item
-    if (!dontDrawItem) {
-        item->d_ptr->initStyleOption(&styleOptionTmp, transform, exposedRegion ? *exposedRegion : QRegion(), exposedRegion == 0);
-
-        bool clipsToShape = (item->d_ptr->flags & QGraphicsItem::ItemClipsToShape);
-        bool savePainter = clipsToShape || painterStateProtection;
+    if (drawItem) {
+        Q_ASSERT(!itemIsFullyTransparent);
+        Q_ASSERT(itemHasContents);
+        item->d_ptr->initStyleOption(&styleOptionTmp, transform, exposedRegion
+                                     ? *exposedRegion : QRegion(), exposedRegion == 0);
+
+        const bool itemClipsToShape = item->d_ptr->flags & QGraphicsItem::ItemClipsToShape;
+        const bool savePainter = itemClipsToShape || painterStateProtection;
         if (savePainter)
             painter->save();
-        if (!childClip)
-            painter->setWorldTransform(transform);
-        if (clipsToShape)
+
+        if (!itemHasChildren || !itemClipsChildrenToShape) {
+            ENSURE_TRANSFORM_PTR
+            painter->setWorldTransform(*transformPtr);
+        }
+        if (itemClipsToShape)
             painter->setClipPath(item->shape(), Qt::IntersectClip);
         painter->setOpacity(opacity);
 
@@ -5217,22 +5227,19 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     }
 
     // Draw children in front
-    if (!dontDrawChildren) {
-        // ### Don't visit children that don't ignore parent opacity if this
-        // item is invisible.
-        for (; i < children->size(); ++i) {
-            QGraphicsItem *child = children->at(i);
+    if (itemHasChildren) {
+        for (; i < item->d_ptr->children.size(); ++i) {
+            QGraphicsItem *child = item->d_ptr->children.at(i);
             if (wasDirtyParentSceneTransform)
                 child->d_ptr->dirtySceneTransform = 1;
-            drawSubtreeRecursive(child, painter, viewTransform, exposedRegion,
-                                 widget, 0, opacity);
+            if (itemIsFullyTransparent && !(child->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity))
+                continue;
+            drawSubtreeRecursive(child, painter, viewTransform, exposedRegion, widget, opacity);
         }
-    } else if (wasDirtyParentSceneTransform) {
-        item->d_ptr->invalidateChildrenSceneTransform();
     }
 
     // Restore child clip
-    if (childClip)
+    if (itemHasChildren && itemClipsChildrenToShape)
         painter->restore();
 }
 
@@ -5525,7 +5532,7 @@ void QGraphicsScene::drawItems(QPainter *painter,
         if (!item->d_ptr->itemDiscovered) {
             topLevelItems << item;
             item->d_ptr->itemDiscovered = 1;
-            d->drawSubtreeRecursive(item, painter, viewTransform, expose, widget);
+            d->drawSubtreeRecursive(item, painter, &viewTransform, expose, widget);
         }
     }
 
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index a8f6699..2f63e5b 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -206,6 +206,7 @@ public:
     void mousePressEventHandler(QGraphicsSceneMouseEvent *mouseEvent);
     QGraphicsWidget *windowForItem(const QGraphicsItem *item) const;
 
+    QList<QGraphicsItem *> topLevelItemsInStackingOrder(const QTransform *const, QRegion *);
     void recursive_items_helper(QGraphicsItem *item, QRectF rect, QList<QGraphicsItem *> *items,
                                 const QTransform &parentTransform, const QTransform &viewTransform,
                                 Qt::ItemSelectionMode mode, Qt::SortOrder order, qreal parentOpacity = 1.0) const;
@@ -259,10 +260,18 @@ public:
     void drawItemHelper(QGraphicsItem *item, QPainter *painter,
                         const QStyleOptionGraphicsItem *option, QWidget *widget,
                         bool painterStateProtection);
-    
-    void drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter, const QTransform &viewTransform,
-                              QRegion *exposedRegion, QWidget *widget,
-                              QList<QGraphicsItem *> *topLevelItems = 0, qreal parentOpacity = qreal(1.0));
+
+    inline void drawItems(QPainter *painter, const QTransform *const viewTransform,
+                          QRegion *exposedRegion, QWidget *widget)
+    {
+        const QList<QGraphicsItem *> tli = topLevelItemsInStackingOrder(viewTransform, exposedRegion);
+        for (int i = 0; i < tli.size(); ++i)
+            drawSubtreeRecursive(tli.at(i), painter, viewTransform, exposedRegion, widget);
+        return;
+    }
+
+    void drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter, const QTransform *const,
+                              QRegion *exposedRegion, QWidget *widget, qreal parentOpacity = qreal(1.0));
     void markDirty(QGraphicsItem *item, const QRectF &rect = QRectF(), bool invalidateChildren = false,
                    bool maybeDirtyClipPath = false, bool force = false, bool ignoreOpacity = false,
                    bool removingItemFromScene = false);
diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp
index 553d71c..1ba87ec 100644
--- a/src/gui/graphicsview/qgraphicsview.cpp
+++ b/src/gui/graphicsview/qgraphicsview.cpp
@@ -3298,8 +3298,8 @@ void QGraphicsView::paintEvent(QPaintEvent *event)
 
     // Items
     if (!(d->optimizationFlags & IndirectPainting)) {
-        d->scene->d_func()->drawSubtreeRecursive(0, &painter, viewTransform, &d->exposedRegion,
-                                                 viewport(), 0);
+        d->scene->d_func()->drawItems(&painter, viewTransformed ? &viewTransform : 0,
+                                      &d->exposedRegion, viewport());
     } else {
         // Find all exposed items
         bool allItems = false;