More re-factoring of Graphics View's update mechanism.

This time with a recursive approach of processing dirty items. I've kept
the previous approach using a dirty list, but the recursive one is now
the default. Use QT_GV_USE_DIRTY_LIST=1 to swap.

I've also cached the item's device transform in both cases so that we
can re-use it later when drawing the item.

4 files changed, 185 insertions, 83 deletions

diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index 12aaba5..c3744b2 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -3769,7 +3769,7 @@ bool QGraphicsItemPrivate::discardUpdateRequest(bool ignoreClipping, bool ignore
     // No scene, or if the scene is updating everything, means we have nothing
     // to do. The only exception is if the scene tracks the growing scene rect.
     return (!visible && !ignoreVisibleBit)
-           || (!ignoreDirtyBit && (dirty || hasDirtyAncestor()))
+           || (!ignoreDirtyBit && dirty)
            || !scene
            || (scene->d_func()->updateAll && scene->d_func()->hasSceneRect)
            || (!ignoreClipping && (childrenClippedToShape() && isClippedAway()))
diff --git a/src/gui/graphicsview/qgraphicsitem_p.h b/src/gui/graphicsview/qgraphicsitem_p.h
index 9d5b58a..deaf30f 100644
--- a/src/gui/graphicsview/qgraphicsitem_p.h
+++ b/src/gui/graphicsview/qgraphicsitem_p.h
@@ -145,6 +145,9 @@ public:
         dirtyChildrenBoundingRect(1),
         inDirtyList(0),
         paintedViewBoundingRectsNeedRepaint(0),
+        allChildrenDirty(0),
+        fullUpdatePending(0),
+        hasValidDeviceTransform(0),
         globalStackingOrder(-1),
         q_ptr(0)
     {
@@ -297,18 +300,6 @@ public:
                || (childrenCombineOpacity() && isFullyTransparent());
     }
 
-    inline bool hasDirtyAncestor() const
-    {
-        QGraphicsItem *p = parent;
-        while (p) {
-            if (p->d_ptr->dirtyChildren || (p->d_ptr->dirty && p->d_ptr->childrenClippedToShape()))
-                return true;
-            p = p->d_ptr->parent;
-        }
-        return false;
-    }
-
-
     QPainterPath cachedClipPath;
     QRectF childrenBoundingRect;
     QRectF needsRepaint;
@@ -320,6 +311,7 @@ public:
     QGraphicsItem *parent;
     QList<QGraphicsItem *> children;
     QTransform *transform;
+    QTransform deviceTransform;
     int siblingIndex;
     int index;
     int depth;
@@ -354,7 +346,10 @@ public:
     quint32 dirtyChildrenBoundingRect : 1;
     quint32 inDirtyList : 1;
     quint32 paintedViewBoundingRectsNeedRepaint : 1;
-    quint32 padding : 18; // feel free to use
+    quint32 allChildrenDirty : 1;
+    quint32 fullUpdatePending : 1;
+    quint32 hasValidDeviceTransform : 1;
+    quint32 padding : 15; // feel free to use
 
     // Optional stacking order
     int globalStackingOrder;
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index eaebd1a..a5ac9d9 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -337,6 +337,7 @@ QGraphicsScenePrivate::QGraphicsScenePrivate()
       hasSceneRect(false),
       updateAll(false),
       calledEmitUpdated(false),
+      processDirtyItemsEmitted(false),
       selectionChanging(0),
       regenerateIndex(true),
       purgePending(false),
@@ -683,73 +684,70 @@ void QGraphicsScenePrivate::_q_polishItems()
 
 void QGraphicsScenePrivate::_q_processDirtyItems()
 {
-    Q_Q(QGraphicsScene);
-    if (dirtyItems.isEmpty())
-        return;
+    static int useDirtyListEnv = qgetenv("QT_GV_USE_DIRTY_LIST").toInt();
+    processDirtyItemsEmitted = false;
 
     if (updateAll) {
-        for (int i = 0; i < dirtyItems.size(); ++i)
-            resetDirtyItem(dirtyItems.at(i));
-        dirtyItems.clear();
+        if (useDirtyListEnv) {
+            for (int i = 0; i < dirtyItems.size(); ++i)
+                resetDirtyItem(dirtyItems.at(i));
+            dirtyItems.clear();
+        }
+        return;
+    }
+
+    if (!useDirtyListEnv) {
+        processDirtyItemsRecursive(0, views.at(0)->viewportTransform());
+        for (int i = 0; i < views.size(); ++i)
+            views.at(i)->d_func()->processPendingUpdates();
         return;
     }
 
-    const bool useCompatUpdate = views.isEmpty() || (connectedSignals & changedSignalMask);
     for (int i = 0; i < dirtyItems.size(); ++i) {
         QGraphicsItem *item = dirtyItems.at(i);
-        if (useCompatUpdate && !item->d_ptr->itemIsUntransformable()
-            && qFuzzyIsNull(item->boundingRegionGranularity())) {
-            // This block of code is kept for compatibility. Since 4.5, by default
-            // QGraphicsView does not connect the signal and we use the below
-            // method of delivering updates.
-            q->update(item->sceneBoundingRect());
-            resetDirtyItem(item);
-            continue;
+        QGraphicsView *view = views.at(0);
+        QGraphicsViewPrivate *viewPrivate = view->d_func();
+        const QTransform deviceTransform = item->deviceTransform(view->viewportTransform());
+
+        QRectF dirtyRect = adjustedItemBoundingRect(item);
+        if (!item->d_ptr->fullUpdatePending) {
+            _q_adjustRect(&item->d_ptr->needsRepaint);
+            dirtyRect &= item->d_ptr->needsRepaint;
         }
 
-        QRectF dirtyRect;
-        bool uninitializedDirtyRect = true;
-
-        for (int j = 0; j < views.size(); ++j) {
-            QGraphicsView *view = views.at(j);
-            QGraphicsViewPrivate *viewPrivate = view->d_func();
-            if (viewPrivate->fullUpdatePending)
-                continue;
-            switch (viewPrivate->viewportUpdateMode) {
-            case QGraphicsView::NoViewportUpdate:
-                continue;
-            case QGraphicsView::FullViewportUpdate:
-                view->viewport()->update();
-                viewPrivate->fullUpdatePending = 1;
-                continue;
-            default:
-                break;
-            }
-
-            if (uninitializedDirtyRect) {
-                dirtyRect = adjustedItemBoundingRect(item);
-                if (!item->d_ptr->dirty) {
-                    _q_adjustRect(&item->d_ptr->needsRepaint);
-                    dirtyRect &= item->d_ptr->needsRepaint;
-                }
-
-                if (item->d_ptr->dirtyChildren && !item->d_ptr->children.isEmpty()
-                    && !item->d_ptr->childrenClippedToShape()) {
-                    QRectF childrenBounds = item->childrenBoundingRect();
-                    _q_adjustRect(&childrenBounds);
-                    dirtyRect |= childrenBounds;
-                }
-                uninitializedDirtyRect = false;
-            }
+        if (item->d_ptr->allChildrenDirty && !item->d_ptr->children.isEmpty()
+            && !item->d_ptr->childrenClippedToShape()) {
+            QRectF childrenBounds = item->childrenBoundingRect();
+            _q_adjustRect(&childrenBounds);
+            dirtyRect |= childrenBounds;
+        }
 
-            if (item->d_ptr->paintedViewBoundingRectsNeedRepaint)
-                viewPrivate->updateRect(item->d_ptr->paintedViewBoundingRects.value(viewPrivate->viewport));
+        if (item->d_ptr->paintedViewBoundingRectsNeedRepaint)
+            viewPrivate->updateRect(item->d_ptr->paintedViewBoundingRects.value(viewPrivate->viewport));
 
-            if (!item->d_ptr->hasBoundingRegionGranularity)
-                viewPrivate->updateRect(viewPrivate->mapToViewRect(item, dirtyRect));
+        bool dirtyRectOutsideViewport = false;
+        if (item->d_ptr->hasBoundingRegionGranularity) {
+            const QRegion dirtyViewRegion = deviceTransform.map(QRegion(dirtyRect.toRect()))
+                                            & viewPrivate->viewport->rect();
+            if (!dirtyViewRegion.isEmpty())
+                viewPrivate->updateRegion(dirtyViewRegion);
             else
-                viewPrivate->updateRegion(viewPrivate->mapToViewRegion(item, dirtyRect));
+                dirtyRectOutsideViewport = true;
+        } else {
+            const QRect dirtyViewRect = deviceTransform.mapRect(dirtyRect).toRect()
+                                        & viewPrivate->viewport->rect();
+            if (!dirtyViewRect.isEmpty())
+                viewPrivate->updateRect(dirtyViewRect);
+            else
+                dirtyRectOutsideViewport = true;
+        }
+        if (!dirtyRectOutsideViewport) {
+            // We know for sure this item will be process in the paint event, hence
+            // store its device transform and re-use it when drawing.
+            item->d_ptr->hasValidDeviceTransform = 1;
+            item->d_ptr->deviceTransform = deviceTransform;
         }
+
         resetDirtyItem(item);
     }
 
@@ -5064,6 +5062,7 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     QTransform transform;
     QRect viewBoundingRect;
     if (item) {
+        if (!item->d_ptr->hasValidDeviceTransform) {
         if (item->d_ptr->itemIsUntransformable()) {
             transform = item->deviceTransform(viewTransform);
         } else {
@@ -5082,6 +5081,10 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
                 transform = parentTransform;
             }
         }
+        } else {
+            transform = item->d_ptr->deviceTransform;
+            item->d_ptr->hasValidDeviceTransform = 0;
+        }
         QRectF brect = item->boundingRect();
         if (!brect.size().isNull()) {
             // ### This does not take the clip into account.
@@ -5176,25 +5179,120 @@ void QGraphicsScenePrivate::markDirty(QGraphicsItem *item, const QRectF &rect, b
     if (!fullItemUpdate && rect.isEmpty())
         return;
 
-    if (dirtyItems.isEmpty())
+    if (!processDirtyItemsEmitted) {
         QMetaObject::invokeMethod(q_ptr, "_q_processDirtyItems", Qt::QueuedConnection);
+        processDirtyItemsEmitted = true;
+    }
+
+    item->d_ptr->dirty = 1;
+    if (fullItemUpdate)
+        item->d_ptr->fullUpdatePending = 1;
+    else if (!item->d_ptr->fullUpdatePending)
+        item->d_ptr->needsRepaint |= rect;
 
-    if (item->d_ptr->inDirtyList) {
-        if (fullItemUpdate)
-            item->d_ptr->dirty = 1;
-        else if (!item->d_ptr->dirty)
-            item->d_ptr->needsRepaint |= rect;
+    if (invalidateChildren) {
+        item->d_ptr->allChildrenDirty = 1;
+        item->d_ptr->dirtyChildren = 1;
+    }
+
+    static int useDirtyListEnv = qgetenv("QT_GV_USE_DIRTY_LIST").toInt();
+    if (useDirtyListEnv) {
+        if (!item->d_ptr->inDirtyList) {
+            dirtyItems.append(item);
+            item->d_ptr->inDirtyList = 1;
+        }
     } else {
-        dirtyItems.append(item);
-        item->d_ptr->inDirtyList = 1;
-        if (fullItemUpdate)
-            item->d_ptr->dirty = 1;
-        else if (!item->d_ptr->dirty)
-            item->d_ptr->needsRepaint = rect;
+        QGraphicsItem *p = item->d_ptr->parent;
+        while (p && !p->d_ptr->dirtyChildren) {
+            p->d_ptr->dirtyChildren = 1;
+            p = p->d_ptr->parent;
+        }
     }
+}
 
-    if (invalidateChildren)
-        item->d_ptr->dirtyChildren = 1;
+void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, const QTransform &parentTransform)
+{
+    Q_ASSERT(!item || item->d_ptr->dirty || item->d_ptr->dirtyChildren);
+
+    // Calculate the full transform for this item.
+    QTransform transform;
+    if (item) {
+        if (item->d_ptr->itemIsUntransformable()) {
+            transform = item->deviceTransform(views.at(0)->viewportTransform());
+        } else {
+            const QPointF &pos = item->d_ptr->pos;
+            bool posNull = pos.isNull();
+            if (!posNull || item->d_ptr->transform) {
+                if (item->d_ptr->transform) {
+                    transform = *item->d_ptr->transform;
+                    if (!posNull)
+                        transform *= QTransform::fromTranslate(pos.x(), pos.y());
+                    transform *= parentTransform;
+                } else {
+                    transform = QTransform::fromTranslate(pos.x(), pos.y()) * parentTransform;
+                }
+            } else {
+                transform = parentTransform;
+            }
+        }
+    } else {
+        transform = parentTransform;
+    }
+
+    // Process item.
+    if (item && item->d_ptr->dirty) {
+        QRectF dirtyRect = adjustedItemBoundingRect(item);
+        if (!item->d_ptr->fullUpdatePending) {
+            _q_adjustRect(&item->d_ptr->needsRepaint);
+            dirtyRect &= item->d_ptr->needsRepaint;
+        }
+
+        QGraphicsViewPrivate *viewPrivate = views.at(0)->d_func();
+        if (item->d_ptr->paintedViewBoundingRectsNeedRepaint)
+            viewPrivate->updateRect(item->d_ptr->paintedViewBoundingRects.value(viewPrivate->viewport));
+
+        bool dirtyRectOutsideViewport = false;
+        if (item->d_ptr->hasBoundingRegionGranularity) {
+            const QRegion dirtyViewRegion = transform.map(QRegion(dirtyRect.toRect()))
+                                            & viewPrivate->viewport->rect();
+            if (!dirtyViewRegion.isEmpty())
+                viewPrivate->updateRegion(dirtyViewRegion);
+            else
+                dirtyRectOutsideViewport = true;
+        } else {
+            const QRect dirtyViewRect = transform.mapRect(dirtyRect).toRect()
+                                         & viewPrivate->viewport->rect();
+            if (!dirtyViewRect.isEmpty())
+                viewPrivate->updateRect(dirtyViewRect);
+            else
+                dirtyRectOutsideViewport = true;
+        }
+        if (!dirtyRectOutsideViewport) {
+            // We know for sure this item will be process in the paint event, hence
+            // store its device transform and re-use it when drawing.
+            item->d_ptr->hasValidDeviceTransform = 1;
+            item->d_ptr->deviceTransform = transform;
+        }
+    }
+
+    // Process root items / children.
+    if (!item || item->d_ptr->dirtyChildren) {
+        QList<QGraphicsItem *> *children = item ? &item->d_ptr->children : &topLevelItems;
+        const bool allChildrenDirty = item && item->d_ptr->allChildrenDirty;
+        for (int i = 0; i < children->size(); ++i) {
+            QGraphicsItem *child = children->at(i);
+            if (allChildrenDirty) {
+                child->d_ptr->dirty = 1;
+            } else if (!child->d_ptr->dirty && !child->d_ptr->dirtyChildren) {
+                resetDirtyItem(child);
+                continue;
+            }
+            processDirtyItemsRecursive(child, transform);
+        }
+    }
+
+    if (item)
+        resetDirtyItem(item);
 }
 
 /*!
@@ -5302,7 +5400,12 @@ void QGraphicsScene::drawItems(QPainter *painter,
         }
 
         // Set up the painter transform
-        painter->setWorldTransform(item->deviceTransform(viewTransform), false);
+        if (item->d_ptr->hasValidDeviceTransform) {
+            painter->setWorldTransform(item->d_ptr->deviceTransform);
+            item->d_ptr->hasValidDeviceTransform = 0;
+        } else {
+            painter->setWorldTransform(item->deviceTransform(viewTransform), false);
+        }
 
         // Save painter
         bool saveState = (d->painterStateProtection || (item->flags() & QGraphicsItem::ItemClipsToShape));
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index bf7ac0a..50c716c 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -105,6 +105,7 @@ public:
     QList<QRectF> updatedRects;
     bool updateAll;
     bool calledEmitUpdated;
+    bool processDirtyItemsEmitted;
 
     QPainterPath selectionArea;
     int selectionChanging;
@@ -257,6 +258,7 @@ public:
                               const QRegion &exposedRegion, QWidget *widget, QGraphicsView::OptimizationFlags optimizationFlags);
     void markDirty(QGraphicsItem *item, const QRectF &rect = QRectF(), bool invalidateChildren = false,
                    bool maybeDirtyClipPath = false, bool force = false, bool ignoreOpacity = false);
+    void processDirtyItemsRecursive(QGraphicsItem *item, const QTransform &);
 
     inline void resetDirtyItem(QGraphicsItem *item)
     {
@@ -266,6 +268,8 @@ public:
         item->d_ptr->dirtyChildren = 0;
         item->d_ptr->inDirtyList = 0;
         item->d_ptr->needsRepaint = QRectF();
+        item->d_ptr->allChildrenDirty = 0;
+        item->d_ptr->fullUpdatePending = 0;
     }
 
     inline void removeFromDirtyItems(QGraphicsItem *item)