7 files changed, 283 insertions, 23 deletions

diff --git a/src/plugins/cpptools/cppfileiterationorder.cpp b/src/plugins/cpptools/cppfileiterationorder.cpp
new file mode 100644
index 0000000000..807e26f8ff
--- /dev/null
+++ b/src/plugins/cpptools/cppfileiterationorder.cpp
@@ -0,0 +1,161 @@
+/****************************************************************************
+**
+** Copyright (C) 2015 The Qt Company Ltd.
+** Contact: http://www.qt.io/licensing
+**
+** This file is part of Qt Creator.
+**
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company.  For licensing terms and
+** conditions see http://www.qt.io/terms-conditions.  For further information
+** use the contact form at http://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 or version 3 as published by the Free
+** Software Foundation and appearing in the file LICENSE.LGPLv21 and
+** LICENSE.LGPLv3 included in the packaging of this file.  Please review the
+** following information to ensure the GNU Lesser General Public License
+** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, The Qt Company gives you certain additional
+** rights.  These rights are described in The Qt Company LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+****************************************************************************/
+
+#include "cppfileiterationorder.h"
+
+#include <utils/qtcassert.h>
+
+namespace CppTools {
+
+FileIterationOrder::Entry::Entry(const QString &filePath,
+                                 const QString &projectPartId,
+                                 int commonPrefixLength,
+                                 int commonProjectPartPrefixLength)
+    : filePath(filePath)
+    , projectPartId(projectPartId)
+    , commonFilePathPrefixLength(commonPrefixLength)
+    , commonProjectPartPrefixLength(commonProjectPartPrefixLength)
+{}
+
+namespace {
+
+bool cmpPrefixLengthAndText(int prefixLength1, int prefixLength2)
+{
+    return prefixLength1 > prefixLength2;
+}
+
+bool cmpLessFilePath(const FileIterationOrder::Entry &first,
+                     const FileIterationOrder::Entry &second)
+{
+    return cmpPrefixLengthAndText(first.commonFilePathPrefixLength,
+                                  second.commonFilePathPrefixLength);
+}
+
+bool cmpLessProjectPartId(const FileIterationOrder::Entry &first,
+                          const FileIterationOrder::Entry &second)
+{
+    return cmpPrefixLengthAndText(first.commonProjectPartPrefixLength,
+                                  second.commonProjectPartPrefixLength);
+}
+
+bool hasProjectPart(const FileIterationOrder::Entry &entry)
+{
+    return !entry.projectPartId.isEmpty();
+}
+
+} // anonymous namespace
+
+bool operator<(const FileIterationOrder::Entry &first, const FileIterationOrder::Entry &second)
+{
+    if (hasProjectPart(first)) {
+        if (hasProjectPart(second)) {
+            if (first.projectPartId == second.projectPartId)
+                return cmpLessFilePath(first, second);
+            else
+                return cmpLessProjectPartId(first, second);
+        } else {
+            return true;
+        }
+    } else {
+        if (hasProjectPart(second))
+            return false;
+        else
+            return cmpLessFilePath(first, second);
+    }
+}
+
+FileIterationOrder::FileIterationOrder()
+{
+}
+
+FileIterationOrder::FileIterationOrder(const QString &referenceFilePath,
+                                       const QString &referenceProjectPartId)
+{
+    setReference(referenceFilePath, referenceProjectPartId);
+}
+
+void FileIterationOrder::setReference(const QString &filePath,
+                                      const QString &projectPartId)
+{
+    m_referenceFilePath = filePath;
+    m_referenceProjectPartId = projectPartId;
+}
+
+bool FileIterationOrder::isValid() const
+{
+    return !m_referenceFilePath.isEmpty();
+}
+
+static int commonPrefixLength(const QString &filePath1, const QString &filePath2)
+{
+    const auto mismatches = std::mismatch(filePath1.begin(),
+                                          filePath1.end(),
+                                          filePath2.begin());
+    return mismatches.first - filePath1.begin();
+}
+
+FileIterationOrder::Entry FileIterationOrder::createEntryFromFilePath(
+        const QString &filePath,
+        const QString &projectPartId) const
+{
+    const int filePrefixLength = commonPrefixLength(m_referenceFilePath, filePath);
+    const int projectPartPrefixLength = commonPrefixLength(m_referenceProjectPartId, projectPartId);
+    return Entry(filePath, projectPartId, filePrefixLength, projectPartPrefixLength);
+}
+
+void FileIterationOrder::insert(const QString &filePath, const QString &projectPartId)
+{
+    const Entry entry = createEntryFromFilePath(filePath, projectPartId);
+    m_set.insert(entry);
+}
+
+void FileIterationOrder::remove(const QString &filePath, const QString &projectPartId)
+{
+    const auto needleElement = createEntryFromFilePath(filePath, projectPartId);
+    const auto range = m_set.equal_range(needleElement);
+
+    const auto toRemove = std::find_if(range.first, range.second, [filePath] (const Entry &entry) {
+        return entry.filePath == filePath;
+    });
+    QTC_ASSERT(toRemove != range.second, return);
+    m_set.erase(toRemove);
+}
+
+QStringList FileIterationOrder::toStringList() const
+{
+    QStringList result;
+
+    for (const auto &entry : m_set)
+        result.append(entry.filePath);
+
+    return result;
+}
+
+} // namespace CppTools
diff --git a/src/plugins/cpptools/cppfileiterationorder.h b/src/plugins/cpptools/cppfileiterationorder.h
new file mode 100644
index 0000000000..aecd17d036
--- /dev/null
+++ b/src/plugins/cpptools/cppfileiterationorder.h
@@ -0,0 +1,84 @@
+/****************************************************************************
+**
+** Copyright (C) 2015 The Qt Company Ltd.
+** Contact: http://www.qt.io/licensing
+**
+** This file is part of Qt Creator.
+**
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company.  For licensing terms and
+** conditions see http://www.qt.io/terms-conditions.  For further information
+** use the contact form at http://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 or version 3 as published by the Free
+** Software Foundation and appearing in the file LICENSE.LGPLv21 and
+** LICENSE.LGPLv3 included in the packaging of this file.  Please review the
+** following information to ensure the GNU Lesser General Public License
+** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, The Qt Company gives you certain additional
+** rights.  These rights are described in The Qt Company LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+****************************************************************************/
+
+#ifndef FILEITERATIONORDER_H
+#define FILEITERATIONORDER_H
+
+#include "cpptools_global.h"
+
+#include <QStringList>
+
+#include <set>
+
+namespace CppTools {
+
+class CPPTOOLS_EXPORT FileIterationOrder {
+public:
+    struct Entry {
+        Entry(const QString &filePath,
+              const QString &projectPartId = QString(),
+              int commonFilePathPrefixLength = 0,
+              int commonProjectPartPrefixLength = 0);
+
+        friend CPPTOOLS_EXPORT bool operator<(const Entry &first, const Entry &second);
+
+        const QString filePath;
+        const QString projectPartId;
+        int commonFilePathPrefixLength = 0;
+        int commonProjectPartPrefixLength = 0;
+    };
+
+    FileIterationOrder();
+    FileIterationOrder(const QString &referenceFilePath,
+                       const QString &referenceProjectPartId);
+
+    void setReference(const QString &filePath, const QString &projectPartId);
+    bool isValid() const;
+
+    void insert(const QString &filePath, const QString &projectPartId = QString());
+    void remove(const QString &filePath, const QString &projectPartId);
+    QStringList toStringList() const;
+
+private:
+    Entry createEntryFromFilePath(const QString &filePath,
+                                  const QString &projectPartId) const;
+
+private:
+    QString m_referenceFilePath;
+    QString m_referenceProjectPartId;
+    std::multiset<Entry> m_set;
+};
+
+CPPTOOLS_EXPORT bool operator<(const FileIterationOrder::Entry &first,
+                               const FileIterationOrder::Entry &second);
+
+} // namespace CppTools
+
+#endif // FILEITERATIONORDER_H
diff --git a/src/plugins/cpptools/cppmodelmanager.cpp b/src/plugins/cpptools/cppmodelmanager.cpp
index 5cd9c98689..0b8ccc8fe6 100644
--- a/src/plugins/cpptools/cppmodelmanager.cpp
+++ b/src/plugins/cpptools/cppmodelmanager.cpp
@@ -796,6 +796,8 @@ void CppModelManager::recalculateProjectPartMappings()
 
         }
     }
+
+    d->m_symbolFinder.clearCache();
 }
 
 void CppModelManager::updateCppEditorDocuments() const
diff --git a/src/plugins/cpptools/cpptools.pro b/src/plugins/cpptools/cpptools.pro
index 61a249026e..b543389456 100644
--- a/src/plugins/cpptools/cpptools.pro
+++ b/src/plugins/cpptools/cpptools.pro
@@ -27,6 +27,7 @@ HEADERS += \
     cppcurrentdocumentfilter.h \
     cppeditoroutline.h \
     cppdoxygen.h \
+    cppfileiterationorder.h \
     cppfilesettingspage.h \
     cppfindreferences.h \
     cppfunctionsfilter.h \
@@ -92,6 +93,7 @@ SOURCES += \
     cppcurrentdocumentfilter.cpp \
     cppeditoroutline.cpp \
     cppdoxygen.cpp \
+    cppfileiterationorder.cpp \
     cppfilesettingspage.cpp \
     cppfindreferences.cpp \
     cppfunctionsfilter.cpp \
diff --git a/src/plugins/cpptools/cpptools.qbs b/src/plugins/cpptools/cpptools.qbs
index 065ea0e4c1..611316c4d9 100644
--- a/src/plugins/cpptools/cpptools.qbs
+++ b/src/plugins/cpptools/cpptools.qbs
@@ -49,6 +49,7 @@ QtcPlugin {
         "cppcurrentdocumentfilter.cpp", "cppcurrentdocumentfilter.h",
         "cppdoxygen.cpp", "cppdoxygen.h",
         "cppeditoroutline.cpp", "cppeditoroutline.h",
+        "cppfileiterationorder.cpp", "cppfileiterationorder.h",
         "cppfilesettingspage.cpp", "cppfilesettingspage.h", "cppfilesettingspage.ui",
         "cppfindreferences.cpp", "cppfindreferences.h",
         "cppfunctionsfilter.cpp", "cppfunctionsfilter.h",
diff --git a/src/plugins/cpptools/symbolfinder.cpp b/src/plugins/cpptools/symbolfinder.cpp
index 26df91bc04..3bc72c00b5 100644
--- a/src/plugins/cpptools/symbolfinder.cpp
+++ b/src/plugins/cpptools/symbolfinder.cpp
@@ -34,6 +34,8 @@
 
 #include "symbolfinder.h"
 
+#include "cppmodelmanager.h"
+
 #include <cplusplus/LookupContext.h>
 
 #include <utils/qtcassert.h>
@@ -357,13 +359,20 @@ QStringList SymbolFinder::fileIterationOrder(const QString &referenceFile, const
             insertCache(referenceFile, doc->fileName());
     }
 
-    QStringList files = m_filePriorityCache.value(referenceFile).values();
+    QStringList files = m_filePriorityCache.value(referenceFile).toStringList();
 
     trackCacheUse(referenceFile);
 
     return files;
 }
 
+void SymbolFinder::clearCache()
+{
+    m_filePriorityCache.clear();
+    m_fileMetaCache.clear();
+    m_recent.clear();
+}
+
 void SymbolFinder::checkCacheConsistency(const QString &referenceFile, const Snapshot &snapshot)
 {
     // We only check for "new" files, which which are in the snapshot but not in the cache.
@@ -376,18 +385,29 @@ void SymbolFinder::checkCacheConsistency(const QString &referenceFile, const Sna
     }
 }
 
+const QString projectPartIdForFile(const QString &filePath)
+{
+    const QList<ProjectPart::Ptr> parts = CppModelManager::instance()->projectPart(filePath);
+    if (!parts.isEmpty())
+        return parts.first()->id();
+    return QString();
+}
+
 void SymbolFinder::clearCache(const QString &referenceFile, const QString &comparingFile)
 {
-    m_filePriorityCache[referenceFile].remove(computeKey(referenceFile, comparingFile),
-                                              comparingFile);
+    m_filePriorityCache[referenceFile].remove(comparingFile, projectPartIdForFile(comparingFile));
     m_fileMetaCache[referenceFile].remove(comparingFile);
 }
 
 void SymbolFinder::insertCache(const QString &referenceFile, const QString &comparingFile)
 {
-    // We want an ordering such that the documents with the most common path appear first.
-    m_filePriorityCache[referenceFile].insert(computeKey(referenceFile, comparingFile),
-                                              comparingFile);
+    FileIterationOrder &order = m_filePriorityCache[referenceFile];
+    if (!order.isValid()) {
+        const auto projectPartId = projectPartIdForFile(referenceFile);
+        order.setReference(referenceFile, projectPartId);
+    }
+    order.insert(comparingFile, projectPartIdForFile(comparingFile));
+
     m_fileMetaCache[referenceFile].insert(comparingFile);
 }
 
@@ -408,14 +428,3 @@ void SymbolFinder::trackCacheUse(const QString &referenceFile)
         m_fileMetaCache.remove(oldest);
     }
 }
-
-int SymbolFinder::computeKey(const QString &referenceFile, const QString &comparingFile)
-{
-    // As similar the path from the comparing file is to the path from the reference file,
-    // the smaller the key is, which is then used for sorting the map.
-    std::pair<QString::const_iterator,
-              QString::const_iterator> r = std::mismatch(referenceFile.begin(),
-                                                         referenceFile.end(),
-                                                         comparingFile.begin());
-    return referenceFile.length() - (r.first - referenceFile.begin());
-}
diff --git a/src/plugins/cpptools/symbolfinder.h b/src/plugins/cpptools/symbolfinder.h
index a71d9ed4d2..45236eb1ad 100644
--- a/src/plugins/cpptools/symbolfinder.h
+++ b/src/plugins/cpptools/symbolfinder.h
@@ -33,10 +33,12 @@
 
 #include "cpptools_global.h"
 
+#include "cppfileiterationorder.h"
+
 #include <QHash>
 #include <QStringList>
-#include <QMultiMap>
-#include <QSet>
+
+#include <set>
 
 namespace CPlusPlus {
 class Class;
@@ -71,19 +73,18 @@ public:
     QList<CPlusPlus::Declaration *> findMatchingDeclaration(const CPlusPlus::LookupContext &context,
                                                             CPlusPlus::Function *functionType);
 
+    void clearCache();
+
 private:
     QStringList fileIterationOrder(const QString &referenceFile,
                                    const CPlusPlus::Snapshot &snapshot);
-
     void checkCacheConsistency(const QString &referenceFile, const CPlusPlus::Snapshot &snapshot);
     void clearCache(const QString &referenceFile, const QString &comparingFile);
     void insertCache(const QString &referenceFile, const QString &comparingFile);
 
     void trackCacheUse(const QString &referenceFile);
 
-    static int computeKey(const QString &referenceFile, const QString &comparingFile);
-
-    QHash<QString, QMultiMap<int, QString> > m_filePriorityCache;
+    QHash<QString, FileIterationOrder> m_filePriorityCache;
     QHash<QString, QSet<QString> > m_fileMetaCache;
     QStringList m_recent;
 };