From 788f5a1242c04762f91eaa7565c07b9865846d88 Mon Sep 17 00:00:00 2001
From: Douglas Gregor <dgregor@apple.com>
Date: Sat, 20 Mar 2010 00:41:21 +0000
Subject: [PATCH] Optimize region-of-interest based cursor walks through the
 preprocessed entities by grouping preprocessed entities by file ID. This
 drastically improves performance of repeated clang_getCursor() calls local
 tests, although it is a bit ugly.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@99015 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/clang/Frontend/ASTUnit.h | 21 ++++++++++++
 tools/CIndex/CIndex.cpp          | 55 ++++++++++++++++++++++++++++----
 2 files changed, 70 insertions(+), 6 deletions(-)

diff --git a/include/clang/Frontend/ASTUnit.h b/include/clang/Frontend/ASTUnit.h
index e9a982bb26..61db323a12 100644
--- a/include/clang/Frontend/ASTUnit.h
+++ b/include/clang/Frontend/ASTUnit.h
@@ -21,6 +21,7 @@
 #include "clang/Index/ASTLocation.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/System/Path.h"
+#include <map>
 #include <string>
 #include <vector>
 #include <cassert>
@@ -47,6 +48,11 @@ using namespace idx;
 /// \brief Utility class for loading a ASTContext from a PCH file.
 ///
 class ASTUnit {
+public:
+  typedef std::map<FileID, std::vector<PreprocessedEntity *> > 
+    PreprocessedEntitiesByFileMap;
+private:
+  
   FileManager FileMgr;
 
   SourceManager                     SourceMgr;
@@ -90,6 +96,15 @@ class ASTUnit {
   /// destroyed.
   llvm::SmallVector<llvm::sys::Path, 4> TemporaryFiles;
 
+  /// \brief A mapping from file IDs to the set of preprocessed entities
+  /// stored in that file. 
+  ///
+  /// FIXME: This is just an optimization hack to avoid searching through
+  /// many preprocessed entities during cursor traversal in the CIndex library.
+  /// Ideally, we would just be able to perform a binary search within the
+  /// list of preprocessed entities.
+  PreprocessedEntitiesByFileMap PreprocessedEntitiesByFile;
+  
   /// \brief Simple hack to allow us to assert that ASTUnit is not being
   /// used concurrently, which is not supported.
   ///
@@ -163,6 +178,12 @@ public:
     return TopLevelDecls;
   }
 
+  /// \brief Retrieve the mapping from File IDs to the preprocessed entities
+  /// within that file.
+  PreprocessedEntitiesByFileMap &getPreprocessedEntitiesByFile() {
+    return PreprocessedEntitiesByFile;
+  }
+  
   // Retrieve the diagnostics associated with this AST
   typedef const StoredDiagnostic * diag_iterator;
   diag_iterator diag_begin() const { return Diagnostics.begin(); }
diff --git a/tools/CIndex/CIndex.cpp b/tools/CIndex/CIndex.cpp
index 7d63d26b92..08882168ff 100644
--- a/tools/CIndex/CIndex.cpp
+++ b/tools/CIndex/CIndex.cpp
@@ -234,6 +234,10 @@ public:
   }
 
   bool Visit(CXCursor Cursor, bool CheckedRegionOfInterest = false);
+  
+  std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
+    getPreprocessedEntities();
+
   bool VisitChildren(CXCursor Parent);
 
   // Declaration visitors
@@ -352,6 +356,48 @@ bool CursorVisitor::Visit(CXCursor Cursor, bool CheckedRegionOfInterest) {
   return false;
 }
 
+std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
+CursorVisitor::getPreprocessedEntities() {
+  PreprocessingRecord &PPRec
+    = *TU->getPreprocessor().getPreprocessingRecord();
+  
+  bool OnlyLocalDecls
+    = !TU->isMainFileAST() && TU->getOnlyLocalDecls();
+  
+  // There is no region of interest; we have to walk everything.
+  if (RegionOfInterest.isInvalid())
+    return std::make_pair(PPRec.begin(OnlyLocalDecls),
+                          PPRec.end(OnlyLocalDecls));
+
+  // Find the file in which the region of interest lands.
+  SourceManager &SM = TU->getSourceManager();
+  std::pair<FileID, unsigned> Begin
+    = SM.getDecomposedInstantiationLoc(RegionOfInterest.getBegin());
+  std::pair<FileID, unsigned> End
+    = SM.getDecomposedInstantiationLoc(RegionOfInterest.getEnd());
+  
+  // The region of interest spans files; we have to walk everything.
+  if (Begin.first != End.first)
+    return std::make_pair(PPRec.begin(OnlyLocalDecls),
+                          PPRec.end(OnlyLocalDecls));
+    
+  ASTUnit::PreprocessedEntitiesByFileMap &ByFileMap
+    = TU->getPreprocessedEntitiesByFile();
+  if (ByFileMap.empty()) {
+    // Build the mapping from files to sets of preprocessed entities.
+    for (PreprocessingRecord::iterator E = PPRec.begin(OnlyLocalDecls),
+                                    EEnd = PPRec.end(OnlyLocalDecls);
+         E != EEnd; ++E) {
+      std::pair<FileID, unsigned> P
+        = SM.getDecomposedInstantiationLoc((*E)->getSourceRange().getBegin());
+      ByFileMap[P.first].push_back(*E);
+    }
+  }
+
+  return std::make_pair(ByFileMap[Begin.first].begin(), 
+                        ByFileMap[Begin.first].end());
+}
+
 /// \brief Visit the children of the given cursor.
 ///
 /// \returns true if the visitation should be aborted, false if it
@@ -415,15 +461,12 @@ bool CursorVisitor::VisitChildren(CXCursor Cursor) {
                        = CXXUnit->getPreprocessor().getPreprocessingRecord()) {
       // FIXME: Once we have the ability to deserialize a preprocessing record,
       // do so.
-      bool OnlyLocalDecls
-        = !CXXUnit->isMainFileAST() && CXXUnit->getOnlyLocalDecls();
-      for (PreprocessingRecord::iterator 
-             E = PPRec->begin(OnlyLocalDecls), 
-             EEnd = PPRec->end(OnlyLocalDecls);
-           E != EEnd; ++E) {
+      PreprocessingRecord::iterator E, EEnd;
+      for (llvm::tie(E, EEnd) = getPreprocessedEntities(); E != EEnd; ++E) {
         if (MacroInstantiation *MI = dyn_cast<MacroInstantiation>(*E)) {
           if (Visit(MakeMacroInstantiationCursor(MI, CXXUnit)))
             return true;
+          
           continue;
         }
         
-- 
2.40.0