Optimized visualRegionForSelection in various item views classes

When the number of selected items is large (a few thousands), the
computation of visualRegionForSelection can take a long time (up to a
few seconds). Analysis with valgrind shows that most of the time is
spent in miRegionOp (in qregion.cpp), which is being called by
QRegion::operator+=. The visualRegionForSelection virtual method being
called only to update the view after selection, we can safely ignore
those item's rectangles outside the viewport, thus both reducing the
number of calls to miRegionOp and the actual cost of each call.

This, however, introduces a behaviour change in
visualRegionForSelection, as the returned region will *not* contain
any rectangle *not* intersecting the viewport.

Reviewed-by: Thierry
Task-number: QTBUG-884

3 files changed, 49 insertions, 18 deletions

diff --git a/src/gui/itemviews/qlistview.cpp b/src/gui/itemviews/qlistview.cpp
index b2def39..39ca75a 100644
--- a/src/gui/itemviews/qlistview.cpp
+++ b/src/gui/itemviews/qlistview.cpp
@@ -1387,6 +1387,9 @@ void QListView::setSelection(const QRect &rect, QItemSelectionModel::SelectionFl
 
 /*!
   \reimp
+
+  Since 4.7, the returned region only contains rectangles intersecting
+  (or included in) the viewport.
 */
 QRegion QListView::visualRegionForSelection(const QItemSelection &selection) const
 {
@@ -1394,6 +1397,7 @@ QRegion QListView::visualRegionForSelection(const QItemSelection &selection) con
     // ### NOTE: this is a potential bottleneck in non-static mode
     int c = d->column;
     QRegion selectionRegion;
+    const QRect &viewportRect = d->viewport->rect();
     for (int i = 0; i < selection.count(); ++i) {
         if (!selection.at(i).isValid())
             continue;
@@ -1405,8 +1409,11 @@ QRegion QListView::visualRegionForSelection(const QItemSelection &selection) con
         int t = selection.at(i).topLeft().row();
         int b = selection.at(i).bottomRight().row();
         if (d->viewMode == IconMode || d->isWrapping()) { // in non-static mode, we have to go through all selected items
-            for (int r = t; r <= b; ++r)
-                selectionRegion += QRegion(visualRect(d->model->index(r, c, parent)));
+            for (int r = t; r <= b; ++r) {
+                const QRect &rect = visualRect(d->model->index(r, c, parent));
+                if (viewportRect.intersects(rect))
+                    selectionRegion += rect;
+            }
         } else { // in static mode, we can optimize a bit
             while (t <= b && d->isHidden(t)) ++t;
             while (b >= t && d->isHidden(b)) --b;
@@ -1414,7 +1421,8 @@ QRegion QListView::visualRegionForSelection(const QItemSelection &selection) con
             const QModelIndex bottom = d->model->index(b, c, parent);
             QRect rect(visualRect(top).topLeft(),
                        visualRect(bottom).bottomRight());
-            selectionRegion += QRegion(rect);
+            if (viewportRect.intersects(rect))
+                selectionRegion += rect;
         }
     }
 
diff --git a/src/gui/itemviews/qtableview.cpp b/src/gui/itemviews/qtableview.cpp
index 702a8bb..43445b4 100644
--- a/src/gui/itemviews/qtableview.cpp
+++ b/src/gui/itemviews/qtableview.cpp
@@ -1858,6 +1858,9 @@ void QTableView::setSelection(const QRect &rect, QItemSelectionModel::SelectionF
 
     Returns the rectangle from the viewport of the items in the given
     \a selection.
+
+    Since 4.7, the returned region only contains rectangles intersecting
+    (or included in) the viewport.
 */
 QRegion QTableView::visualRegionForSelection(const QItemSelection &selection) const
 {
@@ -1867,6 +1870,7 @@ QRegion QTableView::visualRegionForSelection(const QItemSelection &selection) co
         return QRegion();
 
     QRegion selectionRegion;
+    const QRect &viewportRect = d->viewport->rect();
     bool verticalMoved = verticalHeader()->sectionsMoved();
     bool horizontalMoved = horizontalHeader()->sectionsMoved();
 
@@ -1876,8 +1880,11 @@ QRegion QTableView::visualRegionForSelection(const QItemSelection &selection) co
             if (range.parent() != d->root || !range.isValid())
                 continue;
             for (int r = range.top(); r <= range.bottom(); ++r)
-                for (int c = range.left(); c <= range.right(); ++c)
-                    selectionRegion += QRegion(visualRect(d->model->index(r, c, d->root)));
+                for (int c = range.left(); c <= range.right(); ++c) {
+                    const QRect &rangeRect = visualRect(d->model->index(r, c, d->root));
+                    if (viewportRect.intersects(rangeRect))
+                        selectionRegion += rangeRect;
+                }
         }
     } else if (horizontalMoved) {
         for (int i = 0; i < selection.count(); ++i) {
@@ -1889,9 +1896,11 @@ QRegion QTableView::visualRegionForSelection(const QItemSelection &selection) co
             if (top > bottom)
                 qSwap<int>(top, bottom);
             int height = bottom - top;
-            for (int c = range.left(); c <= range.right(); ++c)
-                selectionRegion += QRegion(QRect(columnViewportPosition(c), top,
-                                                 columnWidth(c), height));
+            for (int c = range.left(); c <= range.right(); ++c) {
+                const QRect rangeRect(columnViewportPosition(c), top, columnWidth(c), height);
+                if (viewportRect.intersects(rangeRect))
+                    selectionRegion += rangeRect;
+            }
         }
     } else if (verticalMoved) {
         for (int i = 0; i < selection.count(); ++i) {
@@ -1903,9 +1912,11 @@ QRegion QTableView::visualRegionForSelection(const QItemSelection &selection) co
             if (left > right)
                 qSwap<int>(left, right);
             int width = right - left;
-            for (int r = range.top(); r <= range.bottom(); ++r)
-                selectionRegion += QRegion(QRect(left, rowViewportPosition(r),
-                                                 width, rowHeight(r)));
+            for (int r = range.top(); r <= range.bottom(); ++r) {
+                const QRect rangeRect(left, rowViewportPosition(r), width, rowHeight(r));
+                if (viewportRect.intersects(rangeRect))
+                    selectionRegion += rangeRect;
+            }
         }
     } else { // nothing moved
         const int gridAdjust = showGrid() ? 1 : 0;
@@ -1926,12 +1937,17 @@ QRegion QTableView::visualRegionForSelection(const QItemSelection &selection) co
                 rleft = columnViewportPosition(range.right());
                 rright = columnViewportPosition(range.left()) + columnWidth(range.left());
             }
-            selectionRegion += QRect(QPoint(rleft, rtop), QPoint(rright - 1 - gridAdjust, rbottom - 1 - gridAdjust));
+            const QRect rangeRect(QPoint(rleft, rtop), QPoint(rright - 1 - gridAdjust, rbottom - 1 - gridAdjust));
+            if (viewportRect.intersects(rangeRect))
+                selectionRegion += rangeRect;
             if (d->hasSpans()) {
                 foreach (QSpanCollection::Span *s,
                          d->spans.spansInRect(range.left(), range.top(), range.width(), range.height())) {
-                    if (range.contains(s->top(), s->left(), range.parent()))
-                        selectionRegion += d->visualSpanRect(*s);
+                    if (range.contains(s->top(), s->left(), range.parent())) {
+                        const QRect &visualSpanRect = d->visualSpanRect(*s);
+                        if (viewportRect.intersects(visualSpanRect))
+                            selectionRegion += visualSpanRect;
+                    }
                 }
             }
         }
diff --git a/src/gui/itemviews/qtreeview.cpp b/src/gui/itemviews/qtreeview.cpp
index ada3936..101dafe 100644
--- a/src/gui/itemviews/qtreeview.cpp
+++ b/src/gui/itemviews/qtreeview.cpp
@@ -2271,6 +2271,9 @@ void QTreeView::setSelection(const QRect &rect, QItemSelectionModel::SelectionFl
 /*!
   Returns the rectangle from the viewport of the items in the given
   \a selection.
+
+  Since 4.7, the returned region only contains rectangles intersecting
+  (or included in) the viewport.
 */
 QRegion QTreeView::visualRegionForSelection(const QItemSelection &selection) const
 {
@@ -2279,6 +2282,7 @@ QRegion QTreeView::visualRegionForSelection(const QItemSelection &selection) con
         return QRegion();
 
     QRegion selectionRegion;
+    const QRect &viewportRect = d->viewport->rect();
     for (int i = 0; i < selection.count(); ++i) {
         QItemSelectionRange range = selection.at(i);
         if (!range.isValid())
@@ -2311,13 +2315,16 @@ QRegion QTreeView::visualRegionForSelection(const QItemSelection &selection) con
             qSwap<int>(top, bottom);
         int height = bottom - top + 1;
         if (d->header->sectionsMoved()) {
-            for (int c = range.left(); c <= range.right(); ++c)
-                selectionRegion += QRegion(QRect(columnViewportPosition(c), top,
-                                                 columnWidth(c), height));
+            for (int c = range.left(); c <= range.right(); ++c) {
+                const QRect rangeRect(columnViewportPosition(c), top, columnWidth(c), height);
+                if (viewportRect.intersects(rangeRect))
+                    selectionRegion += rangeRect;
+            }
         } else {
             QRect combined = leftRect|rightRect;
             combined.setX(columnViewportPosition(isRightToLeft() ? range.right() : range.left()));
-            selectionRegion += combined;
+            if (viewportRect.intersects(combined))
+                selectionRegion += combined;
         }
     }
     return selectionRegion;