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

1 files changed, 58 insertions, 0 deletions

diff --git a/src/tests/kfileitemmodeltest.cpp b/src/tests/kfileitemmodeltest.cpp
index 299ca6f92..62ff4fae2 100644
--- a/src/tests/kfileitemmodeltest.cpp
+++ b/src/tests/kfileitemmodeltest.cpp
@@ -89,6 +89,7 @@ private slots:
     void testGeneralParentChildRelationships();
     void testNameRoleGroups();
     void testNameRoleGroupsWithExpandedItems();
+    void testInconsistentModel();
 
 private:
     QStringList itemsInModel() const;
@@ -1404,6 +1405,63 @@ void KFileItemModelTest::testNameRoleGroupsWithExpandedItems()
     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;