Completely re-implement (de-)serialization of declaration

chains. The previous implementation relied heavily on the declaration
chain being stored as a (circular) linked list on disk, as it is in
memory. However, when deserializing from multiple modules, the
different chains could get mixed up, leading to broken declaration chains.

The new solution keeps track of the first and last declarations in the
chain for each module file. When we load a declaration, we search all
of the module files for redeclarations of that declaration, then
splice together all of the lists into a coherent whole (along with any
redeclarations that were actually parsed). 

As a drive-by fix, (de-)serialize the redeclaration chains of
TypedefNameDecls, which had somehow gotten missed previously. Add a
test of this serialization.

This new scheme creates a redeclaration table that is fairly large in
the PCH file (on the order of 400k for Cocoa.h's 12MB PCH file). The
table is mmap'd in and searched via a binary search, but it's still
quite large. A future tweak will eliminate entries for declarations
that have no redeclarations anywhere, and should
drastically reduce the size of this table.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@146841 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 74 insertions, 2 deletions

diff --git a/include/clang/Serialization/ASTBitCodes.h b/include/clang/Serialization/ASTBitCodes.h
index 41ef74ee0a..cce6916b4e 100644
--- a/include/clang/Serialization/ASTBitCodes.h
+++ b/include/clang/Serialization/ASTBitCodes.h
@@ -452,7 +452,11 @@ namespace clang {
       
       /// \brief Record code for an array of all of the (sub)modules that were
       /// imported by the AST file.
-      IMPORTED_MODULES
+      IMPORTED_MODULES,
+      
+      /// \brief Record code for the array describing the first/last local
+      /// redeclarations of each entity.
+      LOCAL_REDECLARATIONS
     };
 
     /// \brief Record types used within a source manager block.
@@ -1190,6 +1194,33 @@ namespace clang {
       CTOR_INITIALIZER_INDIRECT_MEMBER
     };
 
+    /// \brief Describes the redeclarations of a declaration.
+    struct LocalRedeclarationsInfo {
+      DeclID FirstID;      // The ID of the first declaration
+      DeclID FirstLocalID; // The ID of the first local declaration
+      DeclID LastLocalID;  // The ID of the last local declaration
+      
+      friend bool operator<(const LocalRedeclarationsInfo &X,
+                            const LocalRedeclarationsInfo &Y) {
+        return X.FirstID < Y.FirstID;
+      }
+      
+      friend bool operator>(const LocalRedeclarationsInfo &X,
+                            const LocalRedeclarationsInfo &Y) {
+        return X.FirstID > Y.FirstID;
+      }
+      
+      friend bool operator<=(const LocalRedeclarationsInfo &X,
+                             const LocalRedeclarationsInfo &Y) {
+        return X.FirstID <= Y.FirstID;
+      }
+      
+      friend bool operator>=(const LocalRedeclarationsInfo &X,
+                             const LocalRedeclarationsInfo &Y) {
+        return X.FirstID >= Y.FirstID;
+      }
+    };
+
     /// @}
   }
 } // end namespace clang
diff --git a/include/clang/Serialization/ASTReader.h b/include/clang/Serialization/ASTReader.h
index 0947dfc4eb..10ed5dceea 100644
--- a/include/clang/Serialization/ASTReader.h
+++ b/include/clang/Serialization/ASTReader.h
@@ -674,6 +674,17 @@ private:
   /// deeply nested calls when there are many redeclarations.
   std::deque<std::pair<Decl *, serialization::DeclID> > PendingPreviousDecls;
 
+  /// \brief The list of redeclaration chains that still need to be 
+  /// reconstructed.
+  ///
+  /// Each element is the global declaration ID of the first declaration in
+  /// the chain. Elements in this vector should be unique; use 
+  /// PendingDeclChainsKnown to ensure uniqueness.
+  llvm::SmallVector<serialization::DeclID, 16> PendingDeclChains;
+
+  /// \brief Keeps track of the elements added to PendingDeclChains.
+  llvm::SmallSet<serialization::DeclID, 16> PendingDeclChainsKnown;
+
   /// \brief We delay loading the chain of objc categories after recursive
   /// loading of declarations is finished.
   std::vector<std::pair<ObjCInterfaceDecl *, serialization::DeclID> >
@@ -759,6 +770,7 @@ private:
   RecordLocation DeclCursorForID(serialization::DeclID ID,
                                  unsigned &RawLocation);
   void loadDeclUpdateRecords(serialization::DeclID ID, Decl *D);
+  void loadPendingDeclChain(serialization::GlobalDeclID ID);
   void loadObjCChainedCategories(serialization::GlobalDeclID ID,
                                  ObjCInterfaceDecl *D);
 
@@ -1028,6 +1040,15 @@ public:
     return cast_or_null<T>(GetLocalDecl(F, LocalID));
   }
 
+  /// \brief Map a global declaration ID into the declaration ID used to 
+  /// refer to this declaration within the given module fule.
+  ///
+  /// \returns the global ID of the given declaration as known in the given
+  /// module file.
+  serialization::DeclID 
+  mapGlobalIDToModuleFileGlobalID(ModuleFile &M,
+                                  serialization::DeclID GlobalID);
+  
   /// \brief Reads a declaration ID from the given position in a record in the
   /// given module.
   ///
diff --git a/include/clang/Serialization/ASTWriter.h b/include/clang/Serialization/ASTWriter.h
index ab0d1ef3d9..fd581bc452 100644
--- a/include/clang/Serialization/ASTWriter.h
+++ b/include/clang/Serialization/ASTWriter.h
@@ -312,7 +312,11 @@ private:
   /// serialized again. In this case, it is registered here, so that the reader
   /// knows to read the updated version.
   SmallVector<ReplacedDeclInfo, 16> ReplacedDecls;
-
+                    
+  /// \brief The list of local redeclarations of entities that were
+  /// first declared non-locally.
+  SmallVector<serialization::LocalRedeclarationsInfo, 2> LocalRedeclarations;
+                  
   /// \brief Statements that we've encountered while serializing a
   /// declaration or type.
   SmallVector<Stmt *, 16> StmtsToEmit;
diff --git a/include/clang/Serialization/Module.h b/include/clang/Serialization/Module.h
index 16d9779e04..cbac5cd148 100644
--- a/include/clang/Serialization/Module.h
+++ b/include/clang/Serialization/Module.h
@@ -260,6 +260,15 @@ public:
   /// \brief Remapping table for declaration IDs in this module.
   ContinuousRangeMap<uint32_t, int, 2> DeclRemap;
 
+  /// \brief Mapping from the module files that this module file depends on
+  /// to the base declaration ID for that module as it is understood within this
+  /// module.
+  ///
+  /// This is effectively a reverse global-to-local mapping for declaration
+  /// IDs, so that we can interpret a true global ID (for this translation unit)
+  /// as a local ID (for this module file).
+  llvm::DenseMap<ModuleFile *, serialization::DeclID> GlobalToLocalDeclIDs;
+
   /// \brief The number of C++ base specifier sets in this AST file.
   unsigned LocalNumCXXBaseSpecifiers;
 
@@ -286,6 +295,13 @@ public:
   /// \brief Array of file-level DeclIDs sorted by file.
   const serialization::DeclID *FileSortedDecls;
 
+  /// \brief Array of redeclaration information within this module file,
+  /// sorted by the first declaration ID.
+  const serialization::LocalRedeclarationsInfo *RedeclarationsInfo;
+
+  /// \brief The number of redeclaration info entries in RedeclarationsInfo.
+  unsigned LocalNumRedeclarationsInfos;
+  
   // === Types ===
 
   /// \brief The number of types in this AST file.