Rework the detailed preprocessing record to separate preprocessing
entities generated directly by the preprocessor from those loaded from
the external source (e.g., the ASTReader). By separating these two
sets of entities into different vectors, we allow both to grow
independently, and eliminate the need for preallocating all of the
loaded preprocessing entities. This is similar to the way the recent
SourceManager refactoring treats FileIDs and the source location
address space.

As part of this, switch over to building a continuous range map to
track preprocessing entities.




git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@135646 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/clang/Lex/PreprocessingRecord.h b/include/clang/Lex/PreprocessingRecord.h
index 1e09bf8..7b233a0 100644
--- a/include/clang/Lex/PreprocessingRecord.h
+++ b/include/clang/Lex/PreprocessingRecord.h
@@ -269,23 +269,26 @@
     /// were seen.
     std::vector<PreprocessedEntity *> PreprocessedEntities;
     
+    /// \brief The set of preprocessed entities in this record that have been
+    /// loaded from external sources.
+    ///
+    /// The entries in this vector are loaded lazily from the external source,
+    /// and are referenced by the iterator using negative indices.
+    std::vector<PreprocessedEntity *> LoadedPreprocessedEntities;
+    
     /// \brief Mapping from MacroInfo structures to their definitions.
     llvm::DenseMap<const MacroInfo *, MacroDefinition *> MacroDefinitions;
 
     /// \brief External source of preprocessed entities.
     ExternalPreprocessingRecordSource *ExternalSource;
     
-    /// \brief The number of preallocated entities (that are known to the
-    /// external source).
-    unsigned NumPreallocatedEntities;
-    
     /// \brief Whether we have already loaded all of the preallocated entities.
     mutable bool LoadedPreallocatedEntities;
     
     void MaybeLoadPreallocatedEntities() const ;
     
   public:
-    /// \brief Construct 
+    /// \brief Construct a new preprocessing record.
     explicit PreprocessingRecord(bool IncludeNestedMacroExpansions);
     
     /// \brief Allocate memory in the preprocessing record.
@@ -301,47 +304,153 @@
     }
     
     // Iteration over the preprocessed entities.
-    typedef std::vector<PreprocessedEntity *>::iterator iterator;
-    typedef std::vector<PreprocessedEntity *>::const_iterator const_iterator;
+    class iterator {
+      PreprocessingRecord *Self;
+      
+      /// \brief Position within the preprocessed entity sequence.
+      ///
+      /// In a complete iteration, the Position field walks the range [-M, N),
+      /// where negative values are used to indicate preprocessed entities
+      /// loaded from the external source while non-negative values are used to
+      /// indicate preprocessed entities introduced by the current preprocessor.
+      /// However, to provide iteration in source order (for, e.g., chained
+      /// precompiled headers), dereferencing the iterator flips the negative
+      /// values (corresponding to loaded entities), so that position -M 
+      /// corresponds to element 0 in the loaded entities vector, position -M+1
+      /// corresponds to element 1 in the loaded entities vector, etc. This
+      /// gives us a reasonably efficient, source-order walk.
+      int Position;
+      
+    public:
+      typedef PreprocessedEntity *value_type;
+      typedef value_type&         reference;
+      typedef value_type*         pointer;
+      typedef std::random_access_iterator_tag iterator_category;
+      typedef int                 difference_type;
+      
+      iterator() : Self(0), Position(0) { }
+      
+      iterator(PreprocessingRecord *Self, int Position) 
+        : Self(Self), Position(Position) { }
+      
+      reference operator*() const {
+        if (Position < 0)
+          return Self->LoadedPreprocessedEntities.end()[Position];
+        return Self->PreprocessedEntities[Position];
+      }
+    
+      pointer operator->() const {
+        if (Position < 0)
+          return &Self->LoadedPreprocessedEntities.end()[Position];
+        
+        return &Self->PreprocessedEntities[Position];        
+      }
+      
+      reference operator[](difference_type D) {
+        return *(*this + D);
+      }
+      
+      iterator &operator++() {
+        ++Position;
+        return *this;
+      }
+      
+      iterator operator++(int) {
+        iterator Prev(*this);
+        ++Position;
+        return Prev;
+      }
+
+      iterator &operator--() {
+        --Position;
+        return *this;
+      }
+      
+      iterator operator--(int) {
+        iterator Prev(*this);
+        --Position;
+        return Prev;
+      }
+
+      friend bool operator==(const iterator &X, const iterator &Y) {
+        return X.Position == Y.Position;
+      }
+
+      friend bool operator!=(const iterator &X, const iterator &Y) {
+        return X.Position != Y.Position;
+      }
+      
+      friend iterator& operator+=(iterator &X, difference_type D) {
+        X.Position += D;
+        return X;
+      }
+
+      friend iterator& operator-=(iterator &X, difference_type D) {
+        X.Position -= D;
+        return X;
+      }
+
+      friend iterator operator+(iterator X, difference_type D) {
+        X.Position += D;
+        return X;
+      }
+
+      friend iterator operator+(difference_type D, iterator X) {
+        X.Position += D;
+        return X;
+      }
+
+      friend difference_type operator-(const iterator &X, const iterator &Y) {
+        return X.Position - Y.Position;
+      }
+    };
+    friend class iterator;
+    
     iterator begin(bool OnlyLocalEntities = false);
     iterator end(bool OnlyLocalEntities = false);
-    const_iterator begin(bool OnlyLocalEntities = false) const;
-    const_iterator end(bool OnlyLocalEntities = false) const;
 
     /// \brief Add a new preprocessed entity to this record.
     void addPreprocessedEntity(PreprocessedEntity *Entity);
     
     /// \brief Set the external source for preprocessed entities.
-    void SetExternalSource(ExternalPreprocessingRecordSource &Source,
-                           unsigned NumPreallocatedEntities);
+    void SetExternalSource(ExternalPreprocessingRecordSource &Source);
 
     /// \brief Retrieve the external source for preprocessed entities.
     ExternalPreprocessingRecordSource *getExternalSource() const {
       return ExternalSource;
     }
     
-    unsigned getNumPreallocatedEntities() const {
-      return NumPreallocatedEntities;
-    }
-    
+    /// \brief Allocate space for a new set of loaded preprocessed entities.
+    ///
+    /// \returns The index into the set of loaded preprocessed entities, which
+    /// corresponds to the first newly-allocated entity.
+    unsigned allocateLoadedEntities(unsigned NumEntities);
+
     /// \brief Set the preallocated entry at the given index to the given
-    /// preprocessed entity.
-    void SetPreallocatedEntity(unsigned Index, PreprocessedEntity *Entity);
+    /// preprocessed entity, which was loaded from the external source.
+    void setLoadedPreallocatedEntity(unsigned Index, 
+                                     PreprocessedEntity *Entity);
 
     /// \brief Register a new macro definition.
     void RegisterMacroDefinition(MacroInfo *Macro, MacroDefinition *MD);
                            
-    /// \brief Retrieve the preprocessed entity at the given index.
-    PreprocessedEntity *getPreprocessedEntity(unsigned Index) {
-      assert(Index < PreprocessedEntities.size() &&
-             "Out-of-bounds preprocessed entity");
-      return PreprocessedEntities[Index];
+    /// \brief Retrieve the loaded preprocessed entity at the given index.
+    PreprocessedEntity *getLoadedPreprocessedEntity(unsigned Index) {
+      assert(Index < LoadedPreprocessedEntities.size() && 
+             "Out-of bounds loaded preprocessed entity");
+      return LoadedPreprocessedEntities[Index];
+    }
+    
+    /// \brief Determine the number of preprocessed entities that were
+    /// loaded (or can be loaded) from an external source.
+    unsigned getNumLoadedPreprocessedEntities() const {
+      return LoadedPreprocessedEntities.size();
     }
     
     /// \brief Retrieve the macro definition that corresponds to the given
     /// \c MacroInfo.
     MacroDefinition *findMacroDefinition(const MacroInfo *MI);
-    
+        
     virtual void MacroExpands(const Token &Id, const MacroInfo* MI);
     virtual void MacroDefined(const Token &Id, const MacroInfo *MI);
     virtual void MacroUndefined(const Token &Id, const MacroInfo *MI);
diff --git a/include/clang/Serialization/ASTReader.h b/include/clang/Serialization/ASTReader.h
index a024cb8..ae666b7 100644
--- a/include/clang/Serialization/ASTReader.h
+++ b/include/clang/Serialization/ASTReader.h
@@ -604,7 +604,15 @@
   /// have not yet been deserialized to the global offset where the macro
   /// record resides.
   llvm::DenseMap<IdentifierInfo *, uint64_t> UnreadMacroRecordOffsets;
-      
+
+  typedef ContinuousRangeMap<unsigned, std::pair<PerFileData *, int>, 4> 
+    GlobalPreprocessedEntityMapType;
+  
+  /// \brief Mapping from global preprocessing entity IDs to the module in
+  /// which the preprocessed entity resides along with the offset that should be
+  /// added to the global preprocessing entitiy ID to produce a local ID.
+  GlobalPreprocessedEntityMapType GlobalPreprocessedEntityMap;
+  
   /// \name CodeGen-relevant special data
   /// \brief Fields containing data that is relevant to CodeGen.
   //@{
@@ -1043,6 +1051,16 @@
     return static_cast<unsigned>(SelectorsLoaded.size());
   }
 
+  /// \brief Returns the number of preprocessed entities known to the AST
+  /// reader.
+  unsigned getTotalNumPreprocessedEntities() const {
+    unsigned Result = 0;
+    for (unsigned I = 0, N = Chain.size(); I != N; ++I)
+      Result += Chain[I]->NumPreallocatedPreprocessingEntities;
+    
+    return Result;
+  }
+  
   /// \brief Returns the number of macro definitions found in the chain.
   unsigned getTotalNumMacroDefinitions() const {
     return static_cast<unsigned>(MacroDefinitionsLoaded.size());
diff --git a/lib/Frontend/ASTUnit.cpp b/lib/Frontend/ASTUnit.cpp
index f7c6695..26a8808 100644
--- a/lib/Frontend/ASTUnit.cpp
+++ b/lib/Frontend/ASTUnit.cpp
@@ -1545,10 +1545,6 @@
       PreprocessedEntities.empty())
     RealizePreprocessedEntitiesFromPreamble();
   
-  if (PreprocessedEntities.empty())
-    if (PreprocessingRecord *PPRec = PP->getPreprocessingRecord())
-      return PPRec->begin(true);
-  
   return PreprocessedEntities.begin();
 }
 
@@ -1556,11 +1552,7 @@
   if (!PreprocessedEntitiesInPreamble.empty() &&
       PreprocessedEntities.empty())
     RealizePreprocessedEntitiesFromPreamble();
-  
-  if (PreprocessedEntities.empty())
-    if (PreprocessingRecord *PPRec = PP->getPreprocessingRecord())
-      return PPRec->end(true);
-  
+    
   return PreprocessedEntities.end();
 }
 
diff --git a/lib/Lex/PreprocessingRecord.cpp b/lib/Lex/PreprocessingRecord.cpp
index 9f93ab0..6e2216a 100644
--- a/lib/Lex/PreprocessingRecord.cpp
+++ b/lib/Lex/PreprocessingRecord.cpp
@@ -47,42 +47,24 @@
 
 PreprocessingRecord::PreprocessingRecord(bool IncludeNestedMacroExpansions)
   : IncludeNestedMacroExpansions(IncludeNestedMacroExpansions),
-    ExternalSource(0), NumPreallocatedEntities(0), 
-    LoadedPreallocatedEntities(false)
+    ExternalSource(0), LoadedPreallocatedEntities(false)
 {
 }
 
 PreprocessingRecord::iterator 
 PreprocessingRecord::begin(bool OnlyLocalEntities) {
   if (OnlyLocalEntities)
-    return PreprocessedEntities.begin() + NumPreallocatedEntities;
+    return iterator(this, 0);
   
   MaybeLoadPreallocatedEntities();
-  return PreprocessedEntities.begin();
+  return iterator(this, -(int)LoadedPreprocessedEntities.size());
 }
 
 PreprocessingRecord::iterator PreprocessingRecord::end(bool OnlyLocalEntities) {
   if (!OnlyLocalEntities)
     MaybeLoadPreallocatedEntities();
   
-  return PreprocessedEntities.end();
-}
-
-PreprocessingRecord::const_iterator 
-PreprocessingRecord::begin(bool OnlyLocalEntities) const {
-  if (OnlyLocalEntities)
-    return PreprocessedEntities.begin() + NumPreallocatedEntities;
-  
-  MaybeLoadPreallocatedEntities();
-  return PreprocessedEntities.begin();
-}
-
-PreprocessingRecord::const_iterator 
-PreprocessingRecord::end(bool OnlyLocalEntities) const {
-  if (!OnlyLocalEntities)
-    MaybeLoadPreallocatedEntities();
-  
-  return PreprocessedEntities.end();
+  return iterator(this, PreprocessedEntities.size());
 }
 
 void PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
@@ -90,20 +72,25 @@
 }
 
 void PreprocessingRecord::SetExternalSource(
-                                    ExternalPreprocessingRecordSource &Source,
-                                            unsigned NumPreallocatedEntities) {
+                                    ExternalPreprocessingRecordSource &Source) {
   assert(!ExternalSource &&
          "Preprocessing record already has an external source");
   ExternalSource = &Source;
-  this->NumPreallocatedEntities = NumPreallocatedEntities;
-  PreprocessedEntities.insert(PreprocessedEntities.begin(), 
-                              NumPreallocatedEntities, 0);
 }
 
-void PreprocessingRecord::SetPreallocatedEntity(unsigned Index, 
-                                                PreprocessedEntity *Entity) {
-  assert(Index < NumPreallocatedEntities &&"Out-of-bounds preallocated entity");
-  PreprocessedEntities[Index] = Entity;
+unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
+  unsigned Result = LoadedPreprocessedEntities.size();
+  LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size() 
+                                    + NumEntities);
+  return Result;
+}
+
+void 
+PreprocessingRecord::setLoadedPreallocatedEntity(unsigned Index, 
+                                                 PreprocessedEntity *Entity) {
+  assert(Index < LoadedPreprocessedEntities.size() &&
+         "Out-of-bounds preallocated entity");
+  LoadedPreprocessedEntities[Index] = Entity;
 }
 
 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro, 
diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index 884cc15..4465b6b 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -1561,7 +1561,7 @@
                                              Code, Record, BlobStart, BlobLen);
   switch (RecType) {
   case PPD_MACRO_EXPANSION: {
-    if (PreprocessedEntity *PE = PPRec.getPreprocessedEntity(Record[0]))
+    if (PreprocessedEntity *PE = PPRec.getLoadedPreprocessedEntity(Record[0]))
       return PE;
     
     MacroExpansion *ME =
@@ -1569,12 +1569,12 @@
                                  SourceRange(ReadSourceLocation(F, Record[1]),
                                              ReadSourceLocation(F, Record[2])),
                                  getMacroDefinition(Record[4]));
-    PPRec.SetPreallocatedEntity(Record[0], ME);
+    PPRec.setLoadedPreallocatedEntity(Record[0], ME);
     return ME;
   }
       
   case PPD_MACRO_DEFINITION: {
-    if (PreprocessedEntity *PE = PPRec.getPreprocessedEntity(Record[0]))
+    if (PreprocessedEntity *PE = PPRec.getLoadedPreprocessedEntity(Record[0]))
       return PE;
     
     if (Record[1] > MacroDefinitionsLoaded.size()) {
@@ -1593,7 +1593,7 @@
                                             ReadSourceLocation(F, Record[2]),
                                             ReadSourceLocation(F, Record[3])));
       
-      PPRec.SetPreallocatedEntity(Record[0], MD);
+      PPRec.setLoadedPreallocatedEntity(Record[0], MD);
       MacroDefinitionsLoaded[Record[1] - 1] = MD;
       
       if (DeserializationListener)
@@ -1604,7 +1604,7 @@
   }
       
   case PPD_INCLUSION_DIRECTIVE: {
-    if (PreprocessedEntity *PE = PPRec.getPreprocessedEntity(Record[0]))
+    if (PreprocessedEntity *PE = PPRec.getLoadedPreprocessedEntity(Record[0]))
       return PE;
     
     const char *FullFileNameStart = BlobStart + Record[3];
@@ -1622,7 +1622,7 @@
                                        File,
                                  SourceRange(ReadSourceLocation(F, Record[1]),
                                              ReadSourceLocation(F, Record[2])));
-    PPRec.SetPreallocatedEntity(Record[0], ID);
+    PPRec.setLoadedPreallocatedEntity(Record[0], ID);
     return ID;
   }
   }
@@ -2356,22 +2356,43 @@
       break;
     }
 
-    case MACRO_DEFINITION_OFFSETS:
+    case MACRO_DEFINITION_OFFSETS: {
       F.MacroDefinitionOffsets = (const uint32_t *)BlobStart;
       F.NumPreallocatedPreprocessingEntities = Record[0];
       F.LocalNumMacroDefinitions = Record[1];
-        
-      // Introduce the global -> local mapping for identifiers within this AST
-      // file
+
+      // Introduce the global -> local mapping for preprocessed entities within 
+      // this AST file.
+      unsigned StartingID;
+      if (PP) {
+        if (!PP->getPreprocessingRecord())
+          PP->createPreprocessingRecord(true);
+        if (!PP->getPreprocessingRecord()->getExternalSource())
+          PP->getPreprocessingRecord()->SetExternalSource(*this);
+        StartingID 
+          = PP->getPreprocessingRecord()
+              ->allocateLoadedEntities(F.NumPreallocatedPreprocessingEntities);
+      } else {
+        // FIXME: We'll eventually want to kill this path, since it assumes
+        // a particular allocation strategy in the preprocessing record.
+        StartingID = getTotalNumPreprocessedEntities();
+      }
+      
+      GlobalPreprocessedEntityMap.insert(
+                        std::make_pair(StartingID,
+                                         std::make_pair(&F, -(int)StartingID)));
+
+      // Introduce the global -> local mapping for macro definitions within 
+      // this AST file.
       GlobalMacroDefinitionMap.insert(
                std::make_pair(getTotalNumMacroDefinitions() + 1, 
                               std::make_pair(&F, 
                                              -getTotalNumMacroDefinitions())));
       MacroDefinitionsLoaded.resize(
                     MacroDefinitionsLoaded.size() + F.LocalNumMacroDefinitions);
-
       break;
-
+    }
+        
     case DECL_UPDATE_OFFSETS: {
       if (Record.size() % 2 != 0) {
         Error("invalid DECL_UPDATE_OFFSETS block in AST file");
@@ -2558,21 +2579,12 @@
   }
 
   // Allocate space for loaded slocentries, identifiers, decls and types.
-  unsigned TotalNumPreallocatedPreprocessingEntities = 0;
   for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
     TotalNumSLocEntries += Chain[I]->LocalNumSLocEntries;
-    TotalNumPreallocatedPreprocessingEntities +=
-        Chain[I]->NumPreallocatedPreprocessingEntities;
   }
-  if (PP) {
+  if (PP)
     PP->getHeaderSearchInfo().SetExternalLookup(this);
-    if (TotalNumPreallocatedPreprocessingEntities > 0) {
-      if (!PP->getPreprocessingRecord())
-        PP->createPreprocessingRecord(true);
-      PP->getPreprocessingRecord()->SetExternalSource(*this,
-                                     TotalNumPreallocatedPreprocessingEntities);
-    }
-  }
+
   // Preload SLocEntries.
   for (unsigned I = 0, N = PreloadSLocEntries.size(); I != N; ++I) {
     ASTReadResult Result = ReadSLocEntryRecord(PreloadSLocEntries[I]);
@@ -2768,15 +2780,15 @@
 
 void ASTReader::setPreprocessor(Preprocessor &pp) {
   PP = &pp;
-
-  unsigned TotalNum = 0;
-  for (unsigned I = 0, N = Chain.size(); I != N; ++I)
-    TotalNum += Chain[I]->NumPreallocatedPreprocessingEntities;
-  if (TotalNum) {
+  
+  if (unsigned N = getTotalNumPreprocessedEntities()) {
     if (!PP->getPreprocessingRecord())
       PP->createPreprocessingRecord(true);
-    PP->getPreprocessingRecord()->SetExternalSource(*this, TotalNum);
+    PP->getPreprocessingRecord()->SetExternalSource(*this);
+    PP->getPreprocessingRecord()->allocateLoadedEntities(N);
   }
+  
+  PP->getHeaderSearchInfo().SetExternalLookup(this);
 }
 
 void ASTReader::InitializeContext(ASTContext &Ctx) {
diff --git a/lib/Serialization/ASTWriter.cpp b/lib/Serialization/ASTWriter.cpp
index a3a03a5..aaf4678 100644
--- a/lib/Serialization/ASTWriter.cpp
+++ b/lib/Serialization/ASTWriter.cpp
@@ -1801,7 +1801,7 @@
     InclusionAbbrev = Stream.EmitAbbrev(Abbrev);
   }
   
-  unsigned IndexBase = Chain ? PPRec.getNumPreallocatedEntities() : 0;
+  unsigned IndexBase = Chain ? PPRec.getNumLoadedPreprocessedEntities() : 0;
   RecordData Record;
   for (PreprocessingRecord::iterator E = PPRec.begin(Chain),
                                   EEnd = PPRec.end(Chain);
diff --git a/tools/libclang/CIndex.cpp b/tools/libclang/CIndex.cpp
index 50d56fc..81922a9 100644
--- a/tools/libclang/CIndex.cpp
+++ b/tools/libclang/CIndex.cpp
@@ -267,8 +267,14 @@
 
   bool Visit(CXCursor Cursor, bool CheckedRegionOfInterest = false);
   
-  std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
-    getPreprocessedEntities();
+  bool visitPreprocessedEntitiesInRegion();
+
+  template<typename InputIterator>
+  bool visitPreprocessedEntitiesInRegion(InputIterator First, 
+                                         InputIterator Last);
+
+  template<typename InputIterator>
+  bool visitPreprocessedEntities(InputIterator First, InputIterator Last);
 
   bool VisitChildren(CXCursor Parent);
 
@@ -419,8 +425,7 @@
   return false;
 }
 
-std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
-CursorVisitor::getPreprocessedEntities() {
+bool CursorVisitor::visitPreprocessedEntitiesInRegion() {
   PreprocessingRecord &PPRec
     = *AU->getPreprocessor().getPreprocessingRecord();
   
@@ -441,18 +446,20 @@
   }
   
   PreprocessingRecord::iterator StartEntity, EndEntity;
-  if (OnlyLocalDecls) {
-    StartEntity = AU->pp_entity_begin();
-    EndEntity = AU->pp_entity_end();
-  } else {
-    StartEntity = PPRec.begin();
-    EndEntity = PPRec.end();
-  }
-  
+  if (OnlyLocalDecls && AU->pp_entity_begin() != AU->pp_entity_end())
+    return visitPreprocessedEntitiesInRegion(AU->pp_entity_begin(), 
+                                      AU->pp_entity_end());
+  else
+    return visitPreprocessedEntitiesInRegion(PPRec.begin(), PPRec.end());  
+}
+
+template<typename InputIterator>
+bool CursorVisitor::visitPreprocessedEntitiesInRegion(InputIterator First,
+                                                      InputIterator Last) {
   // There is no region of interest; we have to walk everything.
   if (RegionOfInterest.isInvalid())
-    return std::make_pair(StartEntity, EndEntity);
-
+    return visitPreprocessedEntities(First, Last);
+  
   // Find the file in which the region of interest lands.
   SourceManager &SM = AU->getSourceManager();
   std::pair<FileID, unsigned> Begin
@@ -462,22 +469,52 @@
   
   // The region of interest spans files; we have to walk everything.
   if (Begin.first != End.first)
-    return std::make_pair(StartEntity, EndEntity);
-    
+    return visitPreprocessedEntities(First, Last);
+  
   ASTUnit::PreprocessedEntitiesByFileMap &ByFileMap
-    = AU->getPreprocessedEntitiesByFile();
+  = AU->getPreprocessedEntitiesByFile();
   if (ByFileMap.empty()) {
     // Build the mapping from files to sets of preprocessed entities.
-    for (PreprocessingRecord::iterator E = StartEntity; E != EndEntity; ++E) {
+    for (; First != Last; ++First) {
       std::pair<FileID, unsigned> P
-        = SM.getDecomposedInstantiationLoc((*E)->getSourceRange().getBegin());
+        = SM.getDecomposedInstantiationLoc(
+                                        (*First)->getSourceRange().getBegin());
       
-      ByFileMap[P.first].push_back(*E);
+      ByFileMap[P.first].push_back(*First);
+    }
+  }
+  
+  return visitPreprocessedEntities(ByFileMap[Begin.first].begin(), 
+                                   ByFileMap[Begin.first].end());
+}
+
+template<typename InputIterator>
+bool CursorVisitor::visitPreprocessedEntities(InputIterator First,
+                                              InputIterator Last) {
+  for (; First != Last; ++First) {
+    if (MacroExpansion *ME = dyn_cast<MacroExpansion>(*First)) {
+      if (Visit(MakeMacroExpansionCursor(ME, TU)))
+        return true;
+      
+      continue;
+    }
+    
+    if (MacroDefinition *MD = dyn_cast<MacroDefinition>(*First)) {
+      if (Visit(MakeMacroDefinitionCursor(MD, TU)))
+        return true;
+      
+      continue;
+    }
+    
+    if (InclusionDirective *ID = dyn_cast<InclusionDirective>(*First)) {
+      if (Visit(MakeInclusionDirectiveCursor(ID, TU)))
+        return true;
+      
+      continue;
     }
   }
 
-  return std::make_pair(ByFileMap[Begin.first].begin(), 
-                        ByFileMap[Begin.first].end());
+  return false;
 }
 
 /// \brief Visit the children of the given cursor.
@@ -539,33 +576,8 @@
       }
 
       // Walk the preprocessing record.
-      if (CXXUnit->getPreprocessor().getPreprocessingRecord()) {
-        // FIXME: Once we have the ability to deserialize a preprocessing record,
-        // do so.
-        PreprocessingRecord::iterator E, EEnd;
-        for (llvm::tie(E, EEnd) = getPreprocessedEntities(); E != EEnd; ++E) {
-          if (MacroExpansion *ME = dyn_cast<MacroExpansion>(*E)) {
-            if (Visit(MakeMacroExpansionCursor(ME, tu)))
-              return true;
-            
-            continue;
-          }
-          
-          if (MacroDefinition *MD = dyn_cast<MacroDefinition>(*E)) {
-            if (Visit(MakeMacroDefinitionCursor(MD, tu)))
-              return true;
-            
-            continue;
-          }
-          
-          if (InclusionDirective *ID = dyn_cast<InclusionDirective>(*E)) {
-            if (Visit(MakeInclusionDirectiveCursor(ID, tu)))
-              return true;
-            
-            continue;
-          }
-        }
-      }
+      if (CXXUnit->getPreprocessor().getPreprocessingRecord())
+        visitPreprocessedEntitiesInRegion();
     }
     
     return false;