Fixes: Cleanup/Optimize QGraphicsView::findItems.

    RevBy:    Alexis
    AutoTest: Still pass
    Details:  findItems() does almost exactly the same as
              QGraphicsView::items, the only difference is that it checks
              whether we are about to redraw all items. Next step
              is to optimize the items_helper functions.

              The patch does also include a fix for
              ::items/childItems_helper(const QPainterPath ...); it didn't
              take Qt::Intersects/ContainsItemBoundingRect into account
              (in the same fashion as we do in the other helper functions).

3 files changed, 94 insertions, 115 deletions

diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 8a67d24..3db8e35 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -1487,21 +1487,46 @@ QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QPainterPath &p
                                                            Qt::SortOrder order) const
 {
     QList<QGraphicsItem *> items;
+    const QRectF pathRect = _q_adjustedRect(path.controlPointRect());
+
     // The index returns a rough estimate of what items are inside the rect.
     // Refine it by iterating through all returned items.
-    foreach (QGraphicsItem *item, estimateItemsInRect(_q_adjustedRect(path.controlPointRect()))) {
+    foreach (QGraphicsItem *item, estimateItemsInRect(pathRect)) {
         // Find the item's scene transform in a clever way.
         QTransform x = item->sceneTransform();
-        bool ok;
-        QTransform xinv = x.inverted(&ok);
-        if (ok) {
-            QPainterPath mappedPath = xinv.map(path);
-            if (itemCollidesWithPath(item, mappedPath, mode)) {
+        bool keep = false;
+
+        // ### _q_adjustedRect is only needed because QRectF::intersects,
+        // QRectF::contains and QTransform::map() and friends don't work with
+        // flat rectangles.
+        QRectF br = _q_adjustedRect(item->boundingRect());
+        if (mode >= Qt::ContainsItemBoundingRect) {
+            // Path contains/intersects item's bounding rect
+            if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br)))
+                || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) {
                 items << item;
-                if (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)
-                    childItems_helper(&items, item, mappedPath, mode);
+                keep = true;
+            }
+        } else {
+            // Path contains/intersects item's shape
+            if (QRectF_intersects(pathRect, x.mapRect(br))) {
+                bool ok;
+                QTransform xinv = x.inverted(&ok);
+                if (ok) {
+                    if (itemCollidesWithPath(item, xinv.map(path), mode)) {
+                        items << item;
+                        keep = true;
+                    }
+                }
             }
         }
+
+        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
+            bool ok;
+            QTransform xinv = x.inverted(&ok);
+            if (ok)
+                childItems_helper(&items, item, xinv.map(path), mode);
+        }
     }
 
     if (order != Qt::SortOrder(-1))
@@ -1629,29 +1654,46 @@ void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items,
                                               Qt::ItemSelectionMode mode) const
 {
     bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
-    QPainterPath intersectedPath = !parentClip ? path : path.intersected(parent->shape());
-    if (intersectedPath.isEmpty())
+    QRectF pathRect = _q_adjustedRect(path.boundingRect());
+    QRectF r = !parentClip ? pathRect : pathRect.intersected(_q_adjustedRect(parent->boundingRect()));
+    if (r.isEmpty())
         return;
 
     QList<QGraphicsItem *> &children = parent->d_ptr->children;
     for (int i = 0; i < children.size(); ++i) {
         QGraphicsItem *item = children.at(i);
+        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
+            continue;
 
         // Skip invisible items.
         if (!item->d_ptr->visible || qFuzzyCompare(item->effectiveOpacity(), qreal(0.0)))
             continue;
 
-        QTransform x = item->sceneTransform();
-
-        bool ok;
-        QTransform xinv = x.inverted(&ok);
-        if (ok) {
-            QPainterPath mappedPath = xinv.map(path);
-            if (itemCollidesWithPath(item, mappedPath, mode)) {
+        // ### _q_adjustedRect is only needed because QRectF::intersects,
+        // QRectF::contains and QTransform::map() and friends don't work with
+        // flat rectangles.
+        QRectF br = _q_adjustedRect(item->boundingRect());
+        bool keep = false;
+        if (mode >= Qt::ContainsItemBoundingRect) {
+            // Polygon contains/intersects item's bounding rect
+            if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br)))
+                || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) {
                 items->append(item);
-                if (!item->d_ptr->children.isEmpty())
-                    childItems_helper(items, item, mappedPath, mode);
+                keep = true;
             }
+        } else {
+            // Path contains/intersects item's shape
+            if (QRectF_intersects(pathRect, item->mapRectToParent(br))) {
+                if (itemCollidesWithPath(item, item->mapFromParent(path), mode)) {
+                    items->append(item);
+                    keep = true;
+                }
+            }
+        }
+
+        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) {
+            // Recurse into children that clip children.
+            childItems_helper(items, item, item->mapFromParent(path), mode);
         }
     }
 }
diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp
index f88918f..c421417 100644
--- a/src/gui/graphicsview/qgraphicsview.cpp
+++ b/src/gui/graphicsview/qgraphicsview.cpp
@@ -1029,103 +1029,40 @@ void QGraphicsViewPrivate::freeStyleOptionsArray(QStyleOptionGraphicsItem *array
 
 extern QPainterPath qt_regionToPath(const QRegion &region);
 
-QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedRegion,
-                                                       const QTransform &worldTransform,
-                                                       bool *allItems) const
+QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedRegion, bool *allItems) const
 {
     Q_Q(const QGraphicsView);
-    QList<QGraphicsItem *> itemList;
-    QSet<QGraphicsItem *> tmp;
-    bool simpleTransform = worldTransform.type() <= QTransform::TxScale;
-
-    QPainterPath path = qt_regionToPath(exposedRegion);
-    *allItems = path.contains(q->mapFromScene(scene->d_func()->growingItemsBoundingRect).boundingRect());
-    QList<QRectF> exposedRects;
-    QList<QPolygonF> exposedPolys;
-
-    // Transform the exposed viewport rects to scene rects or polygons
-    foreach (const QRect &rect, exposedRegion.rects()) {
-        QPolygonF exposedPoly = q->mapToScene(rect.adjusted(-1, -1, 1, 1));
-        QRectF exposedRect = exposedPoly.boundingRect();
-        if (!simpleTransform)
-            exposedPolys << exposedPoly;
-        exposedRects << exposedRect;
-    }
-
-    // Find which items need to be drawn.
-    if (*allItems) {
+    const QPainterPath exposedPath(qt_regionToPath(exposedRegion));
+    const QPainterPath exposedScenePath(q->mapToScene(exposedPath));
+
+    if (exposedScenePath.contains(scene->d_func()->growingItemsBoundingRect)) {
+        Q_ASSERT(allItems);
+        *allItems = true;
+
         // All items are guaranteed within the exposed region, don't bother using the index.
-        foreach (QGraphicsItem *item, scene->items()) {
+        QList<QGraphicsItem *> itemList(scene->items());
+        int i = 0;
+        while (i < itemList.size()) {
             // But we only want to include items that are visible
-            if (item->isVisible())
-                itemList << item;
-        }
-    } else if (simpleTransform) {
-        // Simple rect lookups will do.
-        if (exposedRects.size() > 1) {
-            foreach (const QRectF &rect, exposedRects) {
-                foreach (QGraphicsItem *item, scene->d_func()->items_helper(rect, Qt::IntersectsItemBoundingRect, Qt::SortOrder(-1) /* don't sort */)) {
-                    if (!tmp.contains(item)) {
-                        tmp << item;
-                        itemList << item;
-                    }
-                }
-            }
-        } else {
-            itemList += scene->d_func()->items_helper(exposedRects[0], Qt::IntersectsItemBoundingRect, Qt::SortOrder(-1) /* don't sort */);
-        }
-    } else {
-        // Polygon lookup is necessary.
-        if (exposedRects.size() > 1) {
-            foreach (const QPolygonF &poly, exposedPolys) {
-                foreach (QGraphicsItem *item, scene->d_func()->items_helper(poly, Qt::IntersectsItemBoundingRect, Qt::SortOrder(-1) /* don't sort */)) {
-                    if (!tmp.contains(item)) {
-                        tmp << item;
-                        itemList << item;
-                    }
-                }
-            }
-        } else {
-            itemList += scene->d_func()->items_helper(exposedPolys[0], Qt::IntersectsItemBoundingRect, Qt::SortOrder(-1) /* don't sort */);
+            if (!itemList.at(i)->isVisible())
+                itemList.removeAt(i);
+            else
+                ++i;
         }
-    }
 
-    // Check for items that ignore inherited transformations, and add them if
-    // necessary.
-    QRectF untr = scene->d_func()->largestUntransformableItem;
-    if (!*allItems && !untr.isNull()) {
-        // Map the largest untransformable item subtree boundingrect from view
-        // to scene coordinates, and use this to expand all exposed rects in
-        // search for untransformable items.
-        QRectF ltri = matrix.inverted().mapRect(untr);
-        ltri.adjust(-untr.width(), -untr.height(), untr.width(), untr.height());
-
-        foreach (const QRect &rect, exposedRegion.rects()) {
-            QRectF exposed = q->mapToScene(rect.adjusted(-1, -1, 1, 1)).boundingRect();
-            exposed.adjust(-ltri.width(), -ltri.height(), ltri.width(), ltri.height());
-
-            foreach (QGraphicsItem *item, scene->d_func()->estimateItemsInRect(exposed)) {
-                if (item->d_ptr->itemIsUntransformable()) {
-                    if (!tmp.contains(item)) {
-                        QPainterPath rectPath;
-                        rectPath.addRect(rect);
-                        QPainterPath path = item->deviceTransform(q->viewportTransform()).inverted().map(rectPath);
-                        if (item->collidesWithPath(path, Qt::IntersectsItemBoundingRect)) {
-                            itemList << item;
-                            tmp << item;
-                        }
-                    }
-                }
-            }
-        }
+        // Sort the items.
+        QGraphicsScenePrivate::sortItems(&itemList, Qt::DescendingOrder, scene->d_func()->sortCacheEnabled);
+        return itemList;
     }
-    tmp.clear();
 
-    // Sort the items.
-    QGraphicsScenePrivate::sortItems(&itemList, Qt::DescendingOrder,
-                                     scene->d_func()->sortCacheEnabled);
+    if (scene->d_func()->largestUntransformableItem.isNull()) {
+        return scene->d_func()->items_helper(exposedScenePath,
+                                             Qt::IntersectsItemBoundingRect,
+                                             Qt::DescendingOrder);
+    }
 
-    return itemList;
+    // NB! Path must be in viewport coordinates.
+    return itemsInArea(exposedPath, Qt::IntersectsItemBoundingRect, Qt::DescendingOrder);
 }
 
 void QGraphicsViewPrivate::generateStyleOptions(const QList<QGraphicsItem *> &itemList,
@@ -2228,7 +2165,8 @@ QList<QGraphicsItem *> QGraphicsView::items() const
     certainly room for improvement.
 */
 QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &path,
-                                                         Qt::ItemSelectionMode mode) const
+                                                         Qt::ItemSelectionMode mode,
+                                                         Qt::SortOrder order) const
 {
     Q_Q(const QGraphicsView);
 
@@ -2278,8 +2216,8 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat
     }
 
     // ### Insertion sort would be faster.
-    QGraphicsScenePrivate::sortItems(&result, Qt::AscendingOrder,
-                                     scene->d_func()->sortCacheEnabled);
+    if (order != Qt::SortOrder(-1))
+        QGraphicsScenePrivate::sortItems(&result, order, scene->d_func()->sortCacheEnabled);
     return result;
 }
 
@@ -3485,7 +3423,7 @@ void QGraphicsView::paintEvent(QPaintEvent *event)
 
     // Find all exposed items
     bool allItems = false;
-    QList<QGraphicsItem *> itemList = d->findItems(exposedRegion, viewTransform, &allItems);
+    QList<QGraphicsItem *> itemList = d->findItems(exposedRegion, &allItems);
 
 #ifdef QGRAPHICSVIEW_DEBUG
     int exposedTime = stopWatch.elapsed();
diff --git a/src/gui/graphicsview/qgraphicsview_p.h b/src/gui/graphicsview/qgraphicsview_p.h
index 2109673..a76279e 100644
--- a/src/gui/graphicsview/qgraphicsview_p.h
+++ b/src/gui/graphicsview/qgraphicsview_p.h
@@ -85,7 +85,8 @@ public:
     qint64 verticalScroll() const;
 
     QList<QGraphicsItem *> itemsInArea(const QPainterPath &path,
-                                       Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const;
+                                       Qt::ItemSelectionMode mode = Qt::IntersectsItemShape,
+                                       Qt::SortOrder = Qt::AscendingOrder) const;
 
     QPointF mousePressItemPoint;
     QPointF mousePressScenePoint;
@@ -172,9 +173,7 @@ public:
     void updateRegion(const QRegion &region);
     bool updateSceneSlotReimplementedChecked;
 
-    QList<QGraphicsItem *> findItems(const QRegion &exposedRegion,
-				     const QTransform &worldTransform,
-                                     bool *allItems) const;
+    QList<QGraphicsItem *> findItems(const QRegion &exposedRegion, bool *allItems) const;
 
     void generateStyleOptions(const QList<QGraphicsItem *> &itemList,
 			      QGraphicsItem **itemArray,