Make the code that removes items from KFileItemModel more robust

When we remove items from the model, we called the function
KFileItemModel::removeItems(const KFileItemList&, RemoveItemsBehavior).
This function then looked up the indexes of the items using the hash
m_items. This is wasteful in the situations when the indexes of the
removed items are known in advance (like when an expanded folder is
collapsed in Details View), and it can cause trouble if one item is
contained in the model multiple times (can happen when searching, and a
file both matches the search and is a child of a folder that matches
the search). Even if expanding folders in the search results list might
not be particularly useful most of the time, it makes sense to make the
model more robust to prevent crashes and other unexpected behavior in
such situations.

This patch makes the following changes to achieve that goal:

* Change the argument of removeItems() from KFileItemList to
  KItemRangeList. To make this work, the "look the indexes up in
  m_items" code is moved from that function to slotItemsDeleted(). In
  the other places where removeItems() is called, the indexes are
  calculated directly (which is not more difficult than determining the
  removed items as a KFileItemList, if one considers that we needed the
  function childItems(KFileItem) for that, which is not needed any more
  with this patch).

* Also removeFilteredChildren() takes a KItemRangeList now. Rather than
  putting the parent KFileItems into a QSet for O(1) lookup (which
  prevents O(N^2) worst case behavior for the entire function), it uses
  a QSet<ItemData*> now, which should even be more efficient (hashing a
  pointer is cheaper than hashing a KFileItem/KUrl).

BUG: 324371
BUG: 325359
FIXED-IN: 4.12.0
REVIEW: 113070

diff --git a/src/kitemviews/kfileitemmodel.cpp b/src/kitemviews/kfileitemmodel.cpp
index d61de00c506e33b30548cc4718722faf29f97c14..ea7ac2fc1bdf166a922de70f70c18b718d344c1d 100644 (file)
--- a/src/kitemviews/kfileitemmodel.cpp
+++ b/src/kitemviews/kfileitemmodel.cpp
@@ -444,11 +444,18 @@ bool KFileItemModel::setExpanded(int index, bool expanded)
         m_expandedDirs.remove(targetUrl);
         m_dirLister->stop(url);
 
         m_expandedDirs.remove(targetUrl);
         m_dirLister->stop(url);
 

-        removeFilteredChildren(KFileItemList() << item);
+        const int parentLevel = expandedParentsCount(index);
+        const int itemCount = m_itemData.count();
+        const int firstChildIndex = index + 1;
+
+        int childIndex = firstChildIndex;
+        while (childIndex < itemCount && expandedParentsCount(childIndex) > parentLevel) {
+            ++childIndex;
+        }
+        const int childrenCount = childIndex - firstChildIndex;

 
 

-        const KFileItemList itemsToRemove = childItems(item);
-        removeFilteredChildren(itemsToRemove);
-        removeItems(itemsToRemove, DeleteItemData);
+        removeFilteredChildren(KItemRangeList() << KItemRange(index, 1 + childrenCount));
+        removeItems(KItemRangeList() << KItemRange(firstChildIndex, childrenCount), DeleteItemData);

     }
 
     return true;
     }
 
     return true;


@@ -551,21 +558,25 @@ void KFileItemModel::applyFilters()
 {
     // Check which shown items from m_itemData must get
     // hidden and hence moved to m_filteredItems.
 {
     // Check which shown items from m_itemData must get
     // hidden and hence moved to m_filteredItems.

-    KFileItemList newFilteredItems;
+    QVector<int> newFilteredIndexes;
+
+    const int itemCount = m_itemData.count();
+    for (int index = 0; index < itemCount; ++index) {
+        ItemData* itemData = m_itemData.at(index);

 
 

-    foreach (ItemData* itemData, m_itemData) {

         // Only filter non-expanded items as child items may never
         // exist without a parent item
         if (!itemData->values.value("isExpanded").toBool()) {
             const KFileItem item = itemData->item;
             if (!m_filter.matches(item)) {
         // Only filter non-expanded items as child items may never
         // exist without a parent item
         if (!itemData->values.value("isExpanded").toBool()) {
             const KFileItem item = itemData->item;
             if (!m_filter.matches(item)) {

-                newFilteredItems.append(item);
+                newFilteredIndexes.append(index);

                 m_filteredItems.insert(item, itemData);
             }
         }
     }
 
                 m_filteredItems.insert(item, itemData);
             }
         }
     }
 

-    removeItems(newFilteredItems, KeepItemData);
+    const KItemRangeList removedRanges = KItemRangeList::fromSortedContainer(newFilteredIndexes);
+    removeItems(removedRanges, KeepItemData);

 
     // Check which hidden items from m_filteredItems should
     // get visible again and hence removed from m_filteredItems.
 
     // Check which hidden items from m_filteredItems should
     // get visible again and hence removed from m_filteredItems.


@@ -584,22 +595,24 @@ void KFileItemModel::applyFilters()
     insertItems(newVisibleItems);
 }
 
     insertItems(newVisibleItems);
 }
 

-void KFileItemModel::removeFilteredChildren(const KFileItemList& parentsList)
+void KFileItemModel::removeFilteredChildren(const KItemRangeList& itemRanges)

 {
 {

-    if (m_filteredItems.isEmpty()) {
+    if (m_filteredItems.isEmpty() || !m_requestRole[ExpandedParentsCountRole]) {
+        // There are either no filtered items, or it is not possible to expand
+        // folders -> there cannot be any filtered children.

         return;
     }
 
         return;
     }
 

-    // First, we put the parent items into a set to provide fast lookup
-    // while iterating over m_filteredItems and prevent quadratic
-    // complexity if there are N parents and N filtered items.
-    const QSet<KFileItem> parents = parentsList.toSet();
+    QSet<ItemData*> parents;
+    foreach (const KItemRange& range, itemRanges) {
+        for (int index = range.index; index < range.index + range.count; ++index) {
+            parents.insert(m_itemData.at(index));
+        }
+    }

 
     QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.begin();
     while (it != m_filteredItems.end()) {
 
     QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.begin();
     while (it != m_filteredItems.end()) {

-        const ItemData* parent = it.value()->parent;
-
-        if (parent && parents.contains(parent->item)) {
+        if (parents.contains(it.value()->parent)) {

             delete it.value();
             it = m_filteredItems.erase(it);
         } else {
             delete it.value();
             it = m_filteredItems.erase(it);
         } else {


@@ -849,29 +862,49 @@ void KFileItemModel::slotItemsDeleted(const KFileItemList& items)
 {
     dispatchPendingItemsToInsert();
 
 {
     dispatchPendingItemsToInsert();
 

-    KFileItemList itemsToRemove = items;
-    if (m_requestRole[ExpandedParentsCountRole]) {
-        // Assure that removing a parent item also results in removing all children
-        foreach (const KFileItem& item, items) {
-            itemsToRemove.append(childItems(item));
-        }
-    }
+    QVector<int> indexesToRemove;
+    indexesToRemove.reserve(items.count());

 
 

-    if (!m_filteredItems.isEmpty()) {
-        foreach (const KFileItem& item, itemsToRemove) {
+    foreach (const KFileItem& item, items) {
+        const KUrl url = item.url();
+        const int index = m_items.value(url, -1);
+        if (index >= 0) {
+            indexesToRemove.append(index);
+        } else {
+            // Probably the item has been filtered.

             QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.find(item);
             if (it != m_filteredItems.end()) {
                 delete it.value();
                 m_filteredItems.erase(it);
             }
         }
             QHash<KFileItem, ItemData*>::iterator it = m_filteredItems.find(item);
             if (it != m_filteredItems.end()) {
                 delete it.value();
                 m_filteredItems.erase(it);
             }
         }

+    }

 
 

-        if (m_requestRole[ExpandedParentsCountRole]) {
-            removeFilteredChildren(itemsToRemove);
+    std::sort(indexesToRemove.begin(), indexesToRemove.end());
+
+    if (m_requestRole[ExpandedParentsCountRole] && !m_expandedDirs.isEmpty()) {
+        // Assure that removing a parent item also results in removing all children
+        QVector<int> indexesToRemoveWithChildren;
+        indexesToRemoveWithChildren.reserve(m_items.count());
+
+        const int itemCount = m_itemData.count();
+        foreach (int index, indexesToRemove) {
+            indexesToRemoveWithChildren.append(index);
+
+            const int parentLevel = expandedParentsCount(index);
+            int childIndex = index + 1;
+            while (childIndex < itemCount && expandedParentsCount(childIndex) > parentLevel) {
+                indexesToRemoveWithChildren.append(childIndex);
+                ++childIndex;
+            }

         }
         }

+
+        indexesToRemove = indexesToRemoveWithChildren;

     }
 
     }
 

-    removeItems(itemsToRemove, DeleteItemData);
+    const KItemRangeList itemRanges = KItemRangeList::fromSortedContainer(indexesToRemove);
+    removeFilteredChildren(itemRanges);
+    removeItems(itemRanges, DeleteItemData);

 }
 
 void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >& items)
 }
 
 void KFileItemModel::slotRefreshItems(const QList<QPair<KFileItem, KFileItem> >& items)


@@ -1061,23 +1094,21 @@ void KFileItemModel::insertItems(QList<ItemData*>& newItems)
 #endif
 }
 
 #endif
 }
 

-void KFileItemModel::removeItems(const KFileItemList& items, RemoveItemsBehavior behavior)
+void KFileItemModel::removeItems(const KItemRangeList& itemRanges, RemoveItemsBehavior behavior)

 {
 {

-#ifdef KFILEITEMMODEL_DEBUG
-    kDebug() << "Removing " << items.count() << "items";
-#endif
+    if (itemRanges.isEmpty()) {
+        return;
+    }

 
     m_groups.clear();
 
 
     m_groups.clear();
 

-    // Step 1: Determine the indexes of the removed items, remove them from
-    //         the hash m_items, and free the ItemData.
-    QList<int> indexesToRemove;
-    indexesToRemove.reserve(items.count());
-    foreach (const KFileItem& item, items) {
-        const KUrl url = item.url();
-        const int index = m_items.value(url, -1);
-        if (index >= 0) {
-            indexesToRemove.append(index);
+    // Step 1: Remove the items from the hash m_items, and free the ItemData.
+    int removedItemsCount = 0;
+    foreach (const KItemRange& range, itemRanges) {
+        removedItemsCount += range.count;
+
+        for (int index = range.index; index < range.index + range.count; ++index) {
+            const KUrl url = m_itemData.at(index)->item.url();

 
             // Prevent repeated expensive rehashing by using QHash::erase(),
             // rather than QHash::remove().
 
             // Prevent repeated expensive rehashing by using QHash::erase(),
             // rather than QHash::remove().


@@ -1092,14 +1123,7 @@ void KFileItemModel::removeItems(const KFileItemList& items, RemoveItemsBehavior
         }
     }
 
         }
     }
 

-    if (indexesToRemove.isEmpty()) {
-        return;
-    }
-
-    std::sort(indexesToRemove.begin(), indexesToRemove.end());
-

     // Step 2: Remove the ItemData pointers from the list m_itemData.
     // Step 2: Remove the ItemData pointers from the list m_itemData.

-    const KItemRangeList itemRanges = KItemRangeList::fromSortedContainer(indexesToRemove);

     int target = itemRanges.at(0).index;
     int source = itemRanges.at(0).index + itemRanges.at(0).count;
     int nextRange = 1;
     int target = itemRanges.at(0).index;
     int source = itemRanges.at(0).index + itemRanges.at(0).count;
     int nextRange = 1;


@@ -1117,7 +1141,7 @@ void KFileItemModel::removeItems(const KFileItemList& items, RemoveItemsBehavior
         }
     }
 
         }
     }
 

-    m_itemData.erase(m_itemData.end() - indexesToRemove.count(), m_itemData.end());
+    m_itemData.erase(m_itemData.end() - removedItemsCount, m_itemData.end());

 
     // Step 3: Adjust indexes in the hash m_items, starting from the
     //         index of the first removed item.
 
     // Step 3: Adjust indexes in the hash m_items, starting from the
     //         index of the first removed item.


@@ -1205,17 +1229,17 @@ int KFileItemModel::expandedParentsCount(const ItemData* data)
 
 void KFileItemModel::removeExpandedItems()
 {
 
 void KFileItemModel::removeExpandedItems()
 {

-    KFileItemList expandedItems;
+    QVector<int> indexesToRemove;

 
     const int maxIndex = m_itemData.count() - 1;
     for (int i = 0; i <= maxIndex; ++i) {
         const ItemData* itemData = m_itemData.at(i);
         if (itemData->parent) {
 
     const int maxIndex = m_itemData.count() - 1;
     for (int i = 0; i <= maxIndex; ++i) {
         const ItemData* itemData = m_itemData.at(i);
         if (itemData->parent) {

-            expandedItems.append(itemData->item);
+            indexesToRemove.append(i);

         }
     }
 
         }
     }
 

-    removeItems(expandedItems, DeleteItemData);
+    removeItems(KItemRangeList::fromSortedContainer(indexesToRemove), DeleteItemData);

     m_expandedDirs.clear();
 
     // Also remove all filtered items which have a parent.
     m_expandedDirs.clear();
 
     // Also remove all filtered items which have a parent.


@@ -1963,23 +1987,6 @@ QList<QPair<int, QVariant> > KFileItemModel::genericStringRoleGroups(const QByte
     return groups;
 }
 
     return groups;
 }
 

-KFileItemList KFileItemModel::childItems(const KFileItem& item) const
-{
-    KFileItemList items;
-
-    int index = m_items.value(item.url(), -1);
-    if (index >= 0) {
-        const int parentLevel = expandedParentsCount(index);
-        ++index;
-        while (index < m_itemData.count() && expandedParentsCount(index) > parentLevel) {
-            items.append(m_itemData.at(index)->item);
-            ++index;
-        }
-    }
-
-    return items;
-}
-

 void KFileItemModel::emitSortProgress(int resolvedCount)
 {
     // Be tolerant against a resolvedCount with a wrong range.
 void KFileItemModel::emitSortProgress(int resolvedCount)
 {
     // Be tolerant against a resolvedCount with a wrong range.

diff --git a/src/kitemviews/kfileitemmodel.h b/src/kitemviews/kfileitemmodel.h
index 50e3e326b6bec2175f1c5e3f9179c64702f83fbf..d005705492e1a0feb4092808eca2f488ac0143ae 100644 (file)
--- a/src/kitemviews/kfileitemmodel.h
+++ b/src/kitemviews/kfileitemmodel.h
@@ -309,7 +309,7 @@ private:
     };
 
     void insertItems(QList<ItemData*>& items);
     };
 
     void insertItems(QList<ItemData*>& items);

-    void removeItems(const KFileItemList& items, RemoveItemsBehavior behavior);
+    void removeItems(const KItemRangeList& itemRanges, RemoveItemsBehavior behavior);

 
     /**
      * Helper method for insertItems() and removeItems(): Creates
 
     /**
      * Helper method for insertItems() and removeItems(): Creates


@@ -389,11 +389,6 @@ private:
      */
     bool isChildItem(int index) const;
 
      */
     bool isChildItem(int index) const;
 

-    /**
-     * @return Recursive list of child items that have \a item as upper most parent.
-     */
-    KFileItemList childItems(const KFileItem& item) const;
-

     /**
      * Is invoked by KFileItemModelRolesUpdater and results in emitting the
      * sortProgress signal with a percent-value of the progress.
     /**
      * Is invoked by KFileItemModelRolesUpdater and results in emitting the
      * sortProgress signal with a percent-value of the progress.


@@ -409,7 +404,7 @@ private:
      * Removes filtered items whose expanded parents have been deleted
      * or collapsed via setExpanded(parentIndex, false).
      */
      * Removes filtered items whose expanded parents have been deleted
      * or collapsed via setExpanded(parentIndex, false).
      */

-    void removeFilteredChildren(const KFileItemList& parentsList);
+    void removeFilteredChildren(const KItemRangeList& parents);

 
     /**
      * Maps the QByteArray-roles to RoleTypes and provides translation- and
 
     /**
      * Maps the QByteArray-roles to RoleTypes and provides translation- and

diff --git a/src/tests/kfileitemmodelbenchmark.cpp b/src/tests/kfileitemmodelbenchmark.cpp
index f72e43edeb982a42518604c9b7918758d21d697f..66918b6eec50bd021da324f00a18a6004f0fe1a6 100644 (file)
--- a/src/tests/kfileitemmodelbenchmark.cpp
+++ b/src/tests/kfileitemmodelbenchmark.cpp
@@ -185,7 +185,7 @@ void KFileItemModelBenchmark::insertAndRemoveManyItems()
         QCOMPARE(model.count(), initialItems.count() + newItems.count());
 
         if (!removedItems.isEmpty()) {
         QCOMPARE(model.count(), initialItems.count() + newItems.count());
 
         if (!removedItems.isEmpty()) {

-            model.removeItems(removedItems, KFileItemModel::DeleteItemData);
+            model.slotItemsDeleted(removedItems);

         }
         QCOMPARE(model.count(), initialItems.count() + newItems.count() - removedItems.count());
     }
         }
         QCOMPARE(model.count(), initialItems.count() + newItems.count() - removedItems.count());
     }

diff --git a/src/tests/kfileitemmodeltest.cpp b/src/tests/kfileitemmodeltest.cpp
index 299ca6f92066984acc22c3462549ad287d6ef6f9..62ff4fae2d705bb9953a01e0a55c3e4cd1e32075 100644 (file)
--- a/src/tests/kfileitemmodeltest.cpp
+++ b/src/tests/kfileitemmodeltest.cpp
@@ -89,6 +89,7 @@ private slots:
     void testGeneralParentChildRelationships();
     void testNameRoleGroups();
     void testNameRoleGroupsWithExpandedItems();
     void testGeneralParentChildRelationships();
     void testNameRoleGroups();
     void testNameRoleGroupsWithExpandedItems();

+    void testInconsistentModel();

 
 private:
     QStringList itemsInModel() const;
 
 private:
     QStringList itemsInModel() const;


@@ -1404,6 +1405,63 @@ void KFileItemModelTest::testNameRoleGroupsWithExpandedItems()
     QCOMPARE(m_model->groups(), expectedGroups);
 }
 
     QCOMPARE(m_model->groups(), expectedGroups);
 }
 

+void KFileItemModelTest::testInconsistentModel()
+{
+    QSet<QByteArray> modelRoles = m_model->roles();
+    modelRoles << "isExpanded" << "isExpandable" << "expandedParentsCount";
+    m_model->setRoles(modelRoles);
+
+    QStringList files;
+    files << "a/b/c1.txt" << "a/b/c2.txt";
+
+    m_testDir->createFiles(files);
+
+    m_model->loadDirectory(m_testDir->url());
+    QVERIFY(QTest::kWaitForSignal(m_model, SIGNAL(itemsInserted(KItemRangeList)), DefaultTimeout));
+    QCOMPARE(itemsInModel(), QStringList() << "a");
+
+    // Expand "a/" and "a/b/".
+    m_model->setExpanded(0, true);
+    QVERIFY(m_model->isExpanded(0));
+    QVERIFY(QTest::kWaitForSignal(m_model, SIGNAL(itemsInserted(KItemRangeList)), DefaultTimeout));
+    QCOMPARE(itemsInModel(), QStringList() << "a" << "b");
+
+    m_model->setExpanded(1, true);
+    QVERIFY(m_model->isExpanded(1));
+    QVERIFY(QTest::kWaitForSignal(m_model, SIGNAL(itemsInserted(KItemRangeList)), DefaultTimeout));
+    QCOMPARE(itemsInModel(), QStringList() << "a" << "b" << "c1.txt" << "c2.txt");
+
+    // Add the files "c1.txt" and "c2.txt" to the model also as top-level items.
+    // Such a thing can in principle happen when performing a search, and there
+    // are files which
+    // (a) match the search string, and
+    // (b) are children of a folder that matches the search string and is expanded.
+    //
+    // Note that the first item in the list of added items must be new (i.e., not
+    // in the model yet). Otherwise, KFileItemModel::slotItemsAdded() will see that
+    // it receives items that are in the model already and ignore them.
+    KUrl url(m_model->directory().url() + "/a2");
+    KFileItem newItem(KFileItem::Unknown, KFileItem::Unknown, url);
+
+    KFileItemList items;
+    items << newItem << m_model->fileItem(2) << m_model->fileItem(3);
+    m_model->slotItemsAdded(m_model->directory(), items);
+    m_model->slotCompleted();
+    QCOMPARE(itemsInModel(), QStringList() << "a" << "b" << "c1.txt" << "c2.txt" << "a2" << "c1.txt" << "c2.txt");
+
+    m_model->setExpanded(0, false);
+
+    // Test that the right items have been removed, see
+    // https://bugs.kde.org/show_bug.cgi?id=324371
+    QCOMPARE(itemsInModel(), QStringList() << "a" << "a2" << "c1.txt" << "c2.txt");
+
+    // Test that resorting does not cause a crash, see
+    // https://bugs.kde.org/show_bug.cgi?id=325359
+    // The crash is not 100% reproducible, but Valgrind will report an invalid memory access.
+    m_model->resortAllItems();
+
+}
+

 QStringList KFileItemModelTest::itemsInModel() const
 {
     QStringList items;
 QStringList KFileItemModelTest::itemsInModel() const
 {
     QStringList items;