C++: Remove class/function/enum extraction from CppLocatorData.

With every single change in a document the corresponding IndexItem
elements were extracted and put into an vector. The locator filters
then used these lists to iterate over and filter them.

This change removes that extraction, and the filtering now directly
iterates over the IndexItem elements with a callback.

The exception is the current document filter, because it also queries
for all declarations. Adding this to the model would result in a higher
memory usage, while that information is only used by this filter.

Change-Id: Ibe445cc11e9f68b5d807348fd46c7cac4aff4c85
Reviewed-by: Nikolai Kosjar <nikolai.kosjar@digia.com>

13 files changed, 139 insertions, 146 deletions

diff --git a/src/plugins/cpptools/builtinindexingsupport.cpp b/src/plugins/cpptools/builtinindexingsupport.cpp
index 60a33ad7ad..fc51ad12f9 100644
--- a/src/plugins/cpptools/builtinindexingsupport.cpp
+++ b/src/plugins/cpptools/builtinindexingsupport.cpp
@@ -125,7 +125,7 @@ public:
                 break;
             if (m_fileNames.isEmpty() || m_fileNames.contains(it.value()->fileName())) {
                 QVector<Core::SearchResultItem> resultItems;
-                search(it.value())->visitAllChildren([&](const IndexItem::Ptr &info) {
+                auto filter = [&](const IndexItem::Ptr &info) -> IndexItem::VisitorResult {
                     if (matcher.indexIn(info->symbolName()) != -1) {
                         QString text = info->symbolName();
                         QString scope = info->symbolScope();
@@ -148,7 +148,10 @@ public:
                         item.userData = qVariantFromValue(info);
                         resultItems << item;
                     }
-                });
+
+                    return IndexItem::Recurse;
+                };
+                search(it.value())->visitAllChildren(filter);
                 if (!resultItems.isEmpty())
                     future.reportResults(resultItems);
             }
diff --git a/src/plugins/cpptools/cppclassesfilter.cpp b/src/plugins/cpptools/cppclassesfilter.cpp
index 5835b4346b..46519f63da 100644
--- a/src/plugins/cpptools/cppclassesfilter.cpp
+++ b/src/plugins/cpptools/cppclassesfilter.cpp
@@ -45,11 +45,6 @@ CppClassesFilter::~CppClassesFilter()
 {
 }
 
-QList<QList<IndexItem::Ptr> > CppClassesFilter::itemsToMatchUserInputAgainst() const
-{
-    return QList<QList<CppTools::IndexItem::Ptr> >() << m_data->classes();
-}
-
 Core::LocatorFilterEntry CppClassesFilter::filterEntryFromIndexItem(IndexItem::Ptr info)
 {
     const QVariant id = qVariantFromValue(info);
diff --git a/src/plugins/cpptools/cppclassesfilter.h b/src/plugins/cpptools/cppclassesfilter.h
index 446a90b7ca..7fd99416a0 100644
--- a/src/plugins/cpptools/cppclassesfilter.h
+++ b/src/plugins/cpptools/cppclassesfilter.h
@@ -34,19 +34,22 @@
 #include "cpplocatordata.h"
 #include "cpplocatorfilter.h"
 
+#include <utils/qtcoverride.h>
+
 namespace CppTools {
 
+// TODO: un-export this
 class CPPTOOLS_EXPORT CppClassesFilter : public Internal::CppLocatorFilter
 {
     Q_OBJECT
 
 public:
-    CppClassesFilter(Internal::CppLocatorData *locatorData);
-    ~CppClassesFilter();
+    CppClassesFilter(CppLocatorData *locatorData);
+    ~CppClassesFilter() QTC_OVERRIDE;
 
-private:
-    QList<QList<CppTools::IndexItem::Ptr> > itemsToMatchUserInputAgainst() const;
-    Core::LocatorFilterEntry filterEntryFromIndexItem(IndexItem::Ptr info);
+protected:
+    IndexItem::ItemType matchTypes() const QTC_OVERRIDE { return IndexItem::Class; }
+    Core::LocatorFilterEntry filterEntryFromIndexItem(IndexItem::Ptr info) QTC_OVERRIDE;
 };
 
 } // namespace CppTools
diff --git a/src/plugins/cpptools/cppcurrentdocumentfilter.cpp b/src/plugins/cpptools/cppcurrentdocumentfilter.cpp
index ef3242c15d..cd20cfdc54 100644
--- a/src/plugins/cpptools/cppcurrentdocumentfilter.cpp
+++ b/src/plugins/cpptools/cppcurrentdocumentfilter.cpp
@@ -78,10 +78,13 @@ QList<Core::LocatorFilterEntry> CppCurrentDocumentFilter::matchesFor(
     if (m_itemsOfCurrentDoc.isEmpty()) {
         Snapshot snapshot = m_modelManager->snapshot();
         Document::Ptr thisDocument = snapshot.document(m_currentFileName);
-        if (thisDocument)
-            search(thisDocument)->visitAllChildren([&](const IndexItem::Ptr &info){
+        if (thisDocument) {
+            IndexItem::Ptr rootNode = search(thisDocument);
+            rootNode->visitAllChildren([&](const IndexItem::Ptr &info) -> IndexItem::VisitorResult {
                 m_itemsOfCurrentDoc.append(info);
+                return IndexItem::Recurse;
             });
+        }
     }
 
     const Qt::CaseSensitivity caseSensitivityForPrefix = caseSensitivity(entry);
diff --git a/src/plugins/cpptools/cppfunctionsfilter.cpp b/src/plugins/cpptools/cppfunctionsfilter.cpp
index ecdb8a971c..883766bc41 100644
--- a/src/plugins/cpptools/cppfunctionsfilter.cpp
+++ b/src/plugins/cpptools/cppfunctionsfilter.cpp
@@ -45,11 +45,6 @@ CppFunctionsFilter::~CppFunctionsFilter()
 {
 }
 
-QList<QList<CppTools::IndexItem::Ptr> > CppFunctionsFilter::itemsToMatchUserInputAgainst() const
-{
-    return QList<QList<CppTools::IndexItem::Ptr> >() << m_data->functions();
-}
-
 Core::LocatorFilterEntry CppFunctionsFilter::filterEntryFromIndexItem(IndexItem::Ptr info)
 {
     const QVariant id = qVariantFromValue(info);
diff --git a/src/plugins/cpptools/cppfunctionsfilter.h b/src/plugins/cpptools/cppfunctionsfilter.h
index ba0f9d49db..d024afc4e1 100644
--- a/src/plugins/cpptools/cppfunctionsfilter.h
+++ b/src/plugins/cpptools/cppfunctionsfilter.h
@@ -33,6 +33,8 @@
 #include "cpplocatordata.h"
 #include "cpplocatorfilter.h"
 
+#include <utils/qtcoverride.h>
+
 namespace CppTools {
 namespace Internal {
 
@@ -42,11 +44,11 @@ class CppFunctionsFilter : public CppLocatorFilter
 
 public:
     CppFunctionsFilter(CppLocatorData *locatorData);
-    ~CppFunctionsFilter();
+    ~CppFunctionsFilter() QTC_OVERRIDE;
 
-private:
-    QList<QList<IndexItem::Ptr> > itemsToMatchUserInputAgainst() const;
-    Core::LocatorFilterEntry filterEntryFromIndexItem(IndexItem::Ptr info);
+protected:
+    IndexItem::ItemType matchTypes() const QTC_OVERRIDE { return IndexItem::Function; }
+    Core::LocatorFilterEntry filterEntryFromIndexItem(IndexItem::Ptr info) QTC_OVERRIDE;
 };
 
 } // namespace Internal
diff --git a/src/plugins/cpptools/cpplocatordata.cpp b/src/plugins/cpptools/cpplocatordata.cpp
index 986834274d..26665916b3 100644
--- a/src/plugins/cpptools/cpplocatordata.cpp
+++ b/src/plugins/cpptools/cpplocatordata.cpp
@@ -33,42 +33,17 @@
 using namespace CppTools;
 using namespace CppTools::Internal;
 
-static const int MaxPendingDocuments = 10;
+enum { MaxPendingDocuments = 10 };
 
-CppLocatorData::CppLocatorData(CppModelManager *modelManager)
-    : m_modelManager(modelManager)
-    , m_strings(CppToolsPlugin::stringTable())
-    , m_search(m_strings)
+CppLocatorData::CppLocatorData()
+    : m_strings(&CppToolsPlugin::stringTable())
+    , m_search(CppToolsPlugin::stringTable())
     , m_pendingDocumentsMutex(QMutex::Recursive)
 {
-    m_search.setSymbolsToSearchFor(SymbolSearcher::Enums
-                                 | SymbolSearcher::Classes
-                                 | SymbolSearcher::Functions);
+    m_search.setSymbolsToSearchFor(SymbolSearcher::Enums |
+                                   SymbolSearcher::Classes |
+                                   SymbolSearcher::Functions);
     m_pendingDocuments.reserve(MaxPendingDocuments);
-
-    connect(m_modelManager, SIGNAL(documentUpdated(CPlusPlus::Document::Ptr)),
-            this, SLOT(onDocumentUpdated(CPlusPlus::Document::Ptr)));
-
-    connect(m_modelManager, SIGNAL(aboutToRemoveFiles(QStringList)),
-            this, SLOT(onAboutToRemoveFiles(QStringList)));
-}
-
-QList<IndexItem::Ptr> CppLocatorData::enums()
-{
-    flushPendingDocument(true);
-    return allIndexItems(m_allEnums);
-}
-
-QList<IndexItem::Ptr> CppLocatorData::classes()
-{
-    flushPendingDocument(true);
-    return allIndexItems(m_allClasses);
-}
-
-QList<IndexItem::Ptr> CppLocatorData::functions()
-{
-    flushPendingDocument(true);
-    return allIndexItems(m_allFunctions);
 }
 
 void CppLocatorData::onDocumentUpdated(const CPlusPlus::Document::Ptr &document)
@@ -93,57 +68,37 @@ void CppLocatorData::onDocumentUpdated(const CPlusPlus::Document::Ptr &document)
 
 void CppLocatorData::onAboutToRemoveFiles(const QStringList &files)
 {
-    QMutexLocker locker(&m_pendingDocumentsMutex);
+    if (files.isEmpty())
+        return;
 
-    for (int i = 0; i < m_pendingDocuments.size(); ) {
-        if (files.contains(m_pendingDocuments.at(i)->fileName()))
-            m_pendingDocuments.remove(i);
-        else
-            ++i;
-    }
+    QMutexLocker locker(&m_pendingDocumentsMutex);
 
     foreach (const QString &file, files) {
-        m_allEnums.remove(file);
-        m_allClasses.remove(file);
-        m_allFunctions.remove(file);
+        m_infosByFile.remove(file);
+
+        for (int i = 0; i < m_pendingDocuments.size(); ++i) {
+            if (m_pendingDocuments.at(i)->fileName() == file) {
+                m_pendingDocuments.remove(i);
+                break;
+            }
+        }
     }
 
-    m_strings.scheduleGC();
+    m_strings->scheduleGC();
+    flushPendingDocument(false);
 }
 
-void CppLocatorData::flushPendingDocument(bool force)
+void CppLocatorData::flushPendingDocument(bool force) const
 {
+    // TODO: move this off the UI thread and into a future.
     QMutexLocker locker(&m_pendingDocumentsMutex);
     if (!force && m_pendingDocuments.size() < MaxPendingDocuments)
         return;
+    if (m_pendingDocuments.isEmpty())
+        return;
 
-    foreach (CPlusPlus::Document::Ptr doc, m_pendingDocuments) {
-        const QString fileName = findOrInsertFilePath(doc->fileName());
-
-        QList<IndexItem::Ptr> resultsEnums;
-        QList<IndexItem::Ptr> resultsClasses;
-        QList<IndexItem::Ptr> resultsFunctions;
-
-        m_search(doc)->visitAllChildren([&](const IndexItem::Ptr &info) {
-            switch (info->type()) {
-            case IndexItem::Enum:
-                resultsEnums.append(info);
-                break;
-            case IndexItem::Class:
-                resultsClasses.append(info);
-                break;
-            case IndexItem::Function:
-                resultsFunctions.append(info);
-                break;
-            default:
-                break;
-            }
-        });
-
-        m_allEnums[fileName] = resultsEnums;
-        m_allClasses[fileName] = resultsClasses;
-        m_allFunctions[fileName] = resultsFunctions;
-    }
+    foreach (CPlusPlus::Document::Ptr doc, m_pendingDocuments)
+        m_infosByFile.insert(findOrInsertFilePath(doc->fileName()), m_search(doc));
 
     m_pendingDocuments.clear();
     m_pendingDocuments.reserve(MaxPendingDocuments);
diff --git a/src/plugins/cpptools/cpplocatordata.h b/src/plugins/cpptools/cpplocatordata.h
index 0feda706c4..97fce390ce 100644
--- a/src/plugins/cpptools/cpplocatordata.h
+++ b/src/plugins/cpptools/cpplocatordata.h
@@ -27,58 +27,66 @@
 **
 ****************************************************************************/
 
-
 #ifndef CPPLOCATORDATA_H
 #define CPPLOCATORDATA_H
 
+#include <functional>
 #include <QHash>
-#include <QVector>
 
 #include <cplusplus/CppDocument.h>
 
+#include "cpptools_global.h"
 #include "cppmodelmanager.h"
 #include "searchsymbols.h"
 #include "stringtable.h"
 
 namespace CppTools {
+
 namespace Internal {
+class CppToolsPlugin;
+} // Internal namespace
 
 class CppLocatorData : public QObject
 {
     Q_OBJECT
-public:
-    explicit CppLocatorData(CppModelManager *modelManager);
 
-    QList<IndexItem::Ptr> enums();
-    QList<IndexItem::Ptr> classes();
-    QList<IndexItem::Ptr> functions();
+    // Only one instance, created by the CppToolsPlugin.
+    CppLocatorData();
+    friend class Internal::CppToolsPlugin;
 
-private slots:
+public:
+    void filterAllFiles(IndexItem::Visitor func) const
+    {
+        flushPendingDocument(true);
+        QMutexLocker locker(&m_pendingDocumentsMutex);
+        QHash<QString, IndexItem::Ptr> infosByFile = m_infosByFile;
+        locker.unlock();
+        for (auto i = infosByFile.constBegin(), ei = infosByFile.constEnd(); i != ei; ++i)
+            if (i.value()->visitAllChildren(func) == IndexItem::Break)
+                return;
+    }
+
+public slots:
     void onDocumentUpdated(const CPlusPlus::Document::Ptr &document);
     void onAboutToRemoveFiles(const QStringList &files);
 
 private:
-    void flushPendingDocument(bool force);
+    void flushPendingDocument(bool force) const;
     QList<IndexItem::Ptr> allIndexItems(const QHash<QString, QList<IndexItem::Ptr>> &items) const;
 
-    QString findOrInsertFilePath(const QString &path)
-    { return m_strings.insert(path); }
+    QString findOrInsertFilePath(const QString &path) const
+    { return m_strings->insert(path); }
 
 private:
-    CppModelManager *m_modelManager;
-
-    StringTable &m_strings; // Used to avoid QString duplication
+    Internal::StringTable *m_strings; // Used to avoid QString duplication
 
-    SearchSymbols m_search;
-    QHash<QString, QList<IndexItem::Ptr> > m_allEnums;
-    QHash<QString, QList<IndexItem::Ptr> > m_allClasses;
-    QHash<QString, QList<IndexItem::Ptr> > m_allFunctions;
+    mutable SearchSymbols m_search;
+    mutable QHash<QString, IndexItem::Ptr> m_infosByFile;
 
     mutable QMutex m_pendingDocumentsMutex;
-    QVector<CPlusPlus::Document::Ptr> m_pendingDocuments;
+    mutable QVector<CPlusPlus::Document::Ptr> m_pendingDocuments;
 };
 
-} // namespace Internal
-} // namespace CppTools
+} // CppTools namespace
 
 #endif // CPPLOCATORDATA_H
diff --git a/src/plugins/cpptools/cpplocatorfilter.cpp b/src/plugins/cpptools/cpplocatorfilter.cpp
index 3c967c4d32..1d36047a84 100644
--- a/src/plugins/cpptools/cpplocatorfilter.cpp
+++ b/src/plugins/cpptools/cpplocatorfilter.cpp
@@ -65,14 +65,6 @@ void CppLocatorFilter::refresh(QFutureInterface<void> &future)
     Q_UNUSED(future)
 }
 
-QList<QList<CppTools::IndexItem::Ptr> > CppLocatorFilter::itemsToMatchUserInputAgainst() const
-{
-    return QList<QList<CppTools::IndexItem::Ptr> >()
-        << m_data->classes()
-        << m_data->functions()
-        << m_data->enums();
-}
-
 static bool compareLexigraphically(const Core::LocatorFilterEntry &a,
                                    const Core::LocatorFilterEntry &b)
 {
@@ -93,16 +85,15 @@ QList<Core::LocatorFilterEntry> CppLocatorFilter::matchesFor(
     bool hasWildcard = (entry.contains(asterisk) || entry.contains(QLatin1Char('?')));
     bool hasColonColon = entry.contains(QLatin1String("::"));
     const Qt::CaseSensitivity caseSensitivityForPrefix = caseSensitivity(entry);
+    const IndexItem::ItemType wanted = matchTypes();
 
-    const QList<QList<CppTools::IndexItem::Ptr> > itemLists = itemsToMatchUserInputAgainst();
-    foreach (const QList<CppTools::IndexItem::Ptr> &items, itemLists) {
-        foreach (IndexItem::Ptr info, items) {
-            if (future.isCanceled())
-                break;
-            const QString matchString = hasColonColon ? info->scopedSymbolName()
-                                                      : info->symbolName();
-            if ((hasWildcard && regexp.exactMatch(matchString))
-                || (!hasWildcard && matcher.indexIn(matchString) != -1)) {
+    m_data->filterAllFiles([&](const IndexItem::Ptr &info) -> IndexItem::VisitorResult {
+        if (future.isCanceled())
+            return IndexItem::Break;
+        if (info->type() & wanted) {
+            const QString matchString = hasColonColon ? info->scopedSymbolName() : info->symbolName();
+            if ((hasWildcard && regexp.exactMatch(matchString)) ||
+                    (!hasWildcard && matcher.indexIn(matchString) != -1)) {
                 const Core::LocatorFilterEntry filterEntry = filterEntryFromIndexItem(info);
                 if (matchString.startsWith(entry, caseSensitivityForPrefix))
                     betterEntries.append(filterEntry);
@@ -110,7 +101,12 @@ QList<Core::LocatorFilterEntry> CppLocatorFilter::matchesFor(
                     goodEntries.append(filterEntry);
             }
         }
-    }
+
+        if (info->type() & IndexItem::Enum)
+            return IndexItem::Continue;
+        else
+            return IndexItem::Recurse;
+    });
 
     if (goodEntries.size() < 1000)
         qStableSort(goodEntries.begin(), goodEntries.end(), compareLexigraphically);
diff --git a/src/plugins/cpptools/cpplocatorfilter.h b/src/plugins/cpptools/cpplocatorfilter.h
index 07d5ce5fb2..dbf7eed6f0 100644
--- a/src/plugins/cpptools/cpplocatorfilter.h
+++ b/src/plugins/cpptools/cpplocatorfilter.h
@@ -54,7 +54,7 @@ public:
     void refresh(QFutureInterface<void> &future);
 
 protected:
-    virtual QList<QList<IndexItem::Ptr> > itemsToMatchUserInputAgainst() const;
+    virtual IndexItem::ItemType matchTypes() const { return IndexItem::All; }
     virtual Core::LocatorFilterEntry filterEntryFromIndexItem(IndexItem::Ptr info);
 
 protected:
diff --git a/src/plugins/cpptools/cpptoolsplugin.cpp b/src/plugins/cpptools/cpptoolsplugin.cpp
index 7e9f1d061d..44179a1fb4 100644
--- a/src/plugins/cpptools/cpptoolsplugin.cpp
+++ b/src/plugins/cpptools/cpptoolsplugin.cpp
@@ -131,7 +131,13 @@ bool CppToolsPlugin::initialize(const QStringList &arguments, QString *error)
     connect(DocumentManager::instance(), SIGNAL(filesChangedInternally(QStringList)),
             modelManager, SLOT(updateSourceFiles(QStringList)));
 
-    CppLocatorData *locatorData = new CppLocatorData(modelManager);
+    CppLocatorData *locatorData = new CppLocatorData;
+    connect(modelManager, SIGNAL(documentUpdated(CPlusPlus::Document::Ptr)),
+            locatorData, SLOT(onDocumentUpdated(CPlusPlus::Document::Ptr)));
+
+    connect(modelManager, SIGNAL(aboutToRemoveFiles(QStringList)),
+            locatorData, SLOT(onAboutToRemoveFiles(QStringList)));
+
     addAutoReleasedObject(locatorData);
     addAutoReleasedObject(new CppLocatorFilter(locatorData));
     addAutoReleasedObject(new CppClassesFilter(locatorData));
diff --git a/src/plugins/cpptools/indexitem.cpp b/src/plugins/cpptools/indexitem.cpp
index 66784975d0..4790378479 100644
--- a/src/plugins/cpptools/indexitem.cpp
+++ b/src/plugins/cpptools/indexitem.cpp
@@ -44,12 +44,3 @@ void IndexItem::squeeze()
     for (int i = 0, ei = m_children.size(); i != ei; ++i)
         m_children[i]->squeeze();
 }
-
-void IndexItem::visitAllChildren(std::function<void (const IndexItem::Ptr &)> f) const
-{
-    foreach (const IndexItem::Ptr &child, m_children) {
-        f(child);
-        if (!child->m_children.isEmpty())
-            child->visitAllChildren(f);
-    }
-}
diff --git a/src/plugins/cpptools/indexitem.h b/src/plugins/cpptools/indexitem.h
index 2ebf070f4b..40b9782e8c 100644
--- a/src/plugins/cpptools/indexitem.h
+++ b/src/plugins/cpptools/indexitem.h
@@ -38,6 +38,8 @@
 #include <QSharedPointer>
 #include <QMetaType>
 
+#include <functional>
+
 namespace CppTools {
 
 class CPPTOOLS_EXPORT IndexItem
@@ -45,7 +47,14 @@ class CPPTOOLS_EXPORT IndexItem
     Q_DISABLE_COPY(IndexItem)
 
 public:
-    enum ItemType { Enum, Class, Function, Declaration };
+    enum ItemType {
+        Enum        = 1 << 0,
+        Class       = 1 << 1,
+        Function    = 1 << 2,
+        Declaration = 1 << 3,
+
+        All = Enum | Class | Function | Declaration
+    };
 
 private:
     IndexItem(const QString &symbolName,
@@ -139,7 +148,34 @@ public:
     void addChild(IndexItem::Ptr childItem) { m_children.append(childItem); }
     void squeeze();
 
-    void visitAllChildren(std::function<void (const IndexItem::Ptr &)> f) const;
+    enum VisitorResult {
+        Break, /// terminates traversal
+        Continue, /// continues traversal with the next sibling
+        Recurse, /// continues traversal with the children
+    };
+
+    typedef std::function<VisitorResult (const IndexItem::Ptr &)> Visitor;
+
+    VisitorResult visitAllChildren(Visitor callback) const
+    {
+        VisitorResult result = Recurse;
+        foreach (const IndexItem::Ptr &child, m_children) {
+            result = callback(child);
+            switch (result) {
+            case Break:
+                return Break;
+            case Continue:
+                continue;
+            case Recurse:
+                if (!child->m_children.isEmpty()) {
+                    result = child->visitAllChildren(callback);
+                    if (result == Break)
+                        return Break;
+                }
+            }
+        }
+        return result;
+    }
 
 private:
     QString m_symbolName; // as found in the code, therefore might be qualified