Fixed the sorting of search results

The search results window assumed the files were searched in sorted
order, which is not always the case especially since "find usages" can
now operate in several threads.

This change makes sure that the list of files in the search results is
always sorted, using a binary search to find the right index to insert
new files.

Reviewed-by: con

5 files changed, 58 insertions, 29 deletions

diff --git a/src/plugins/find/searchresulttreeitems.cpp b/src/plugins/find/searchresulttreeitems.cpp
index b2c19ec9ca..38ce47f269 100644
--- a/src/plugins/find/searchresulttreeitems.cpp
+++ b/src/plugins/find/searchresulttreeitems.cpp
@@ -92,6 +92,23 @@ const SearchResultTreeItem *SearchResultTreeItem::parent() const
     return m_parent;
 }
 
+static bool compareResultFiles(SearchResultTreeItem *a, SearchResultTreeItem *b)
+{
+    return static_cast<SearchResultFile *>(a)->fileName() <
+            static_cast<SearchResultFile *>(b)->fileName();
+}
+
+int SearchResultTreeItem::insertionIndex(SearchResultFile *child) const
+{
+    Q_ASSERT(m_type == Root);
+    return qLowerBound(m_children.begin(), m_children.end(), child, compareResultFiles) - m_children.begin();
+}
+
+void SearchResultTreeItem::insertChild(int index, SearchResultTreeItem *child)
+{
+    m_children.insert(index, child);
+}
+
 void SearchResultTreeItem::appendChild(SearchResultTreeItem *child)
 {
     m_children.append(child);
@@ -147,7 +164,7 @@ QString SearchResultFile::fileName() const
 }
 
 void SearchResultFile::appendResultLine(int index, int lineNumber, const QString &rowText, int searchTermStart,
-        int searchTermLength)
+                                        int searchTermLength)
 {
     SearchResultTreeItem *child = new SearchResultTextRow(index, lineNumber, rowText,
                                                           searchTermStart, searchTermLength, this);
diff --git a/src/plugins/find/searchresulttreeitems.h b/src/plugins/find/searchresulttreeitems.h
index 6db2efbe0f..e618aeefa2 100644
--- a/src/plugins/find/searchresulttreeitems.h
+++ b/src/plugins/find/searchresulttreeitems.h
@@ -38,6 +38,7 @@ namespace Find {
 namespace Internal {
 
 class SearchResultTreeItem;
+class SearchResultFile;
 
 class SearchResultTreeItem
 {
@@ -55,6 +56,8 @@ public:
     ItemType itemType() const;
     const SearchResultTreeItem *parent() const;
     SearchResultTreeItem *childAt(int index) const;
+    int insertionIndex(SearchResultFile *child) const;
+    void insertChild(int index, SearchResultTreeItem *child);
     void appendChild(SearchResultTreeItem *child);
     int childrenCount() const;
     int rowOfItem() const;
diff --git a/src/plugins/find/searchresulttreemodel.cpp b/src/plugins/find/searchresulttreemodel.cpp
index 3afb91d31d..3d55f70130 100644
--- a/src/plugins/find/searchresulttreemodel.cpp
+++ b/src/plugins/find/searchresulttreemodel.cpp
@@ -43,7 +43,7 @@ using namespace Find::Internal;
 
 SearchResultTreeModel::SearchResultTreeModel(QObject *parent)
     : QAbstractItemModel(parent)
-    , m_lastAppendedResultFile(0)
+    , m_lastAddedResultFile(0)
     , m_showReplaceUI(false)
 {
     m_rootItem = new SearchResultTreeItem;
@@ -277,52 +277,62 @@ QVariant SearchResultTreeModel::headerData(int section, Qt::Orientation orientat
     return QVariant();
 }
 
-void SearchResultTreeModel::appendResultFile(const QString &fileName)
+/**
+ * Adds a file to the list of results and returns the index at which it was inserted.
+ */
+int SearchResultTreeModel::addResultFile(const QString &fileName)
 {
 #ifdef Q_OS_WIN
     if (fileName.contains(QLatin1Char('\\')))
         qWarning("SearchResultTreeModel::appendResultFile: File name with native separators added %s.\n", qPrintable(fileName));
 #endif
-    m_lastAppendedResultFile = new SearchResultFile(fileName, m_rootItem);
+    m_lastAddedResultFile = new SearchResultFile(fileName, m_rootItem);
 
     if (m_showReplaceUI) {
-        m_lastAppendedResultFile->setIsUserCheckable(true);
-        m_lastAppendedResultFile->setCheckState(Qt::Checked);
+        m_lastAddedResultFile->setIsUserCheckable(true);
+        m_lastAddedResultFile->setCheckState(Qt::Checked);
     }
 
-    const int childrenCount = m_rootItem->childrenCount();
-    beginInsertRows(QModelIndex(), childrenCount, childrenCount);
-    m_rootItem->appendChild(m_lastAppendedResultFile);
+    const int index = m_rootItem->insertionIndex(m_lastAddedResultFile);
+    beginInsertRows(QModelIndex(), index, index);
+    m_rootItem->insertChild(index, m_lastAddedResultFile);
     endInsertRows();
+    return index;
 }
 
 void SearchResultTreeModel::appendResultLine(int index, int lineNumber, const QString &rowText,
                                              int searchTermStart, int searchTermLength)
 {
-    if (!m_lastAppendedResultFile)
+    if (!m_lastAddedResultFile)
         return;
 
-    QModelIndex lastFile(createIndex(m_lastAppendedResultFile->rowOfItem(), 0, m_lastAppendedResultFile));
+    QModelIndex lastFile(createIndex(m_lastAddedResultFile->rowOfItem(), 0, m_lastAddedResultFile));
 
-    beginInsertRows(lastFile, m_lastAppendedResultFile->childrenCount(), m_lastAppendedResultFile->childrenCount());
-    m_lastAppendedResultFile->appendResultLine(index, lineNumber, rowText, searchTermStart, searchTermLength);
+    beginInsertRows(lastFile, m_lastAddedResultFile->childrenCount(), m_lastAddedResultFile->childrenCount());
+    m_lastAddedResultFile->appendResultLine(index, lineNumber, rowText, searchTermStart, searchTermLength);
     endInsertRows();
 
     dataChanged(lastFile, lastFile); // Make sure that the number after the file name gets updated
 }
 
-void SearchResultTreeModel::appendResultLine(int index, const QString &fileName, int lineNumber, const QString &rowText,
-                                             int searchTermStart, int searchTermLength)
+/**
+ * Adds the search result to the list of results, creating a new file entry when
+ * necessary. Returns the insertion index when a new file entry was created.
+ */
+int SearchResultTreeModel::addResultLine(int index, const QString &fileName, int lineNumber, const QString &rowText,
+                                         int searchTermStart, int searchTermLength)
 {
-    if (!m_lastAppendedResultFile || (m_lastAppendedResultFile->fileName() != fileName))
-        appendResultFile(fileName);
+    int insertionIndex = -1;
+    if (!m_lastAddedResultFile || (m_lastAddedResultFile->fileName() != fileName))
+        insertionIndex = addResultFile(fileName);
 
     appendResultLine(index, lineNumber, rowText, searchTermStart, searchTermLength);
+    return insertionIndex;
 }
 
 void SearchResultTreeModel::clear()
 {
-    m_lastAppendedResultFile = NULL;
+    m_lastAddedResultFile = NULL;
     m_rootItem->clearChildren();
     reset();
 }
diff --git a/src/plugins/find/searchresulttreemodel.h b/src/plugins/find/searchresulttreemodel.h
index f5b0fea20d..e1622ffbcc 100644
--- a/src/plugins/find/searchresulttreemodel.h
+++ b/src/plugins/find/searchresulttreemodel.h
@@ -69,20 +69,20 @@ signals:
 
 public slots:
     void clear();
-    void appendResultLine(int index, int lineNumber, const QString &rowText,
-                          int searchTermStart, int searchTermLength);
-    void appendResultLine(int index, const QString &fileName, int lineNumber, const QString &rowText,
-                          int searchTermStart, int searchTermLength);
+    int addResultLine(int index, const QString &fileName, int lineNumber, const QString &rowText,
+                      int searchTermStart, int searchTermLength);
 
 private:
-    void appendResultFile(const QString &fileName);
+    void appendResultLine(int index, int lineNumber, const QString &rowText,
+                          int searchTermStart, int searchTermLength);
+    int addResultFile(const QString &fileName);
     QVariant data(const SearchResultTextRow *row, int role) const;
     QVariant data(const SearchResultFile *file, int role) const;
     void initializeData();
     void disposeData();
 
     SearchResultTreeItem *m_rootItem;
-    SearchResultFile *m_lastAppendedResultFile;
+    SearchResultFile *m_lastAddedResultFile;
     QFont m_textEditorFont;
     bool m_showReplaceUI;
 };
diff --git a/src/plugins/find/searchresulttreeview.cpp b/src/plugins/find/searchresulttreeview.cpp
index e05360a435..9eb9923d9b 100644
--- a/src/plugins/find/searchresulttreeview.cpp
+++ b/src/plugins/find/searchresulttreeview.cpp
@@ -68,12 +68,11 @@ void SearchResultTreeView::clear()
 void SearchResultTreeView::appendResultLine(int index, const QString &fileName, int lineNumber, const QString &rowText,
                                             int searchTermStart, int searchTermLength)
 {
-    int rowsBefore = m_model->rowCount();
-    m_model->appendResultLine(index, fileName, lineNumber, rowText, searchTermStart, searchTermLength);
-    int rowsAfter = m_model->rowCount();
+    int insertionIndex = m_model->addResultLine(index, fileName, lineNumber, rowText,
+                                                searchTermStart, searchTermLength);
 
-    if (m_autoExpandResults && (rowsAfter > rowsBefore))
-        setExpanded(model()->index(model()->rowCount() - 1, 0), true);
+    if (m_autoExpandResults && insertionIndex != -1)
+        setExpanded(model()->index(insertionIndex, 0), true);
 }
 
 void SearchResultTreeView::emitJumpToSearchResult(const QModelIndex &index)