Completely re-implement (de-)serialization of redeclaration

chains, again. The prior implementation was very linked-list oriented, and
the list-splicing logic was both fairly convoluted (when loading from
multiple modules) and failed to preserve a reasonable ordering for the
redeclaration chains.

This new implementation uses a simpler strategy, where we store the
ordered redeclaration chains in an array-like structure (indexed based
on the first declaration), and use that ordering to add individual
deserialized declarations to the end of the existing chain. That way,
the chain mimics the ordering from its modules, and a bug somewhere is
far less likely to result in a broken linked list.


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

5 files changed, 154 insertions, 136 deletions

diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index 2417845ff7..7fc5a1d777 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -2396,15 +2396,20 @@ ASTReader::ReadASTBlock(ModuleFile &F) {
       }
       break;
     }
-        
+
     case LOCAL_REDECLARATIONS: {
-      if (F.LocalNumRedeclarationsInfos != 0) {
-        Error("duplicate LOCAL_REDECLARATIONS record in AST file");
+      F.RedeclarationChains.swap(Record);
+      break;
+    }
+        
+    case LOCAL_REDECLARATIONS_MAP: {
+      if (F.LocalNumRedeclarationsInMap != 0) {
+        Error("duplicate LOCAL_REDECLARATIONS_MAP record in AST file");
         return Failure;
       }
       
-      F.LocalNumRedeclarationsInfos = Record[0];
-      F.RedeclarationsInfo = (const LocalRedeclarationsInfo *)BlobStart;
+      F.LocalNumRedeclarationsInMap = Record[0];
+      F.RedeclarationsMap = (const LocalRedeclarationsInfo *)BlobStart;
       break;
     }
         
@@ -6118,7 +6123,6 @@ void ASTReader::ClearSwitchCaseIDs() {
 
 void ASTReader::finishPendingActions() {
   while (!PendingIdentifierInfos.empty() ||
-         !PendingPreviousDecls.empty() ||
          !PendingDeclChains.empty() ||
          !PendingChainedObjCCategories.empty()) {
 
@@ -6130,13 +6134,6 @@ void ASTReader::finishPendingActions() {
       PendingIdentifierInfos.pop_front();
     }
   
-    // Ready to load previous declarations of Decls that were delayed.
-    while (!PendingPreviousDecls.empty()) {
-      loadAndAttachPreviousDecl(PendingPreviousDecls.front().first,
-                                PendingPreviousDecls.front().second);
-      PendingPreviousDecls.pop_front();
-    }
-  
     // Load pending declaration chains.
     for (unsigned I = 0; I != PendingDeclChains.size(); ++I) {
       loadPendingDeclChain(PendingDeclChains[I]);
diff --git a/lib/Serialization/ASTReaderDecl.cpp b/lib/Serialization/ASTReaderDecl.cpp
index d701d60a51..6788d9ee5c 100644
--- a/lib/Serialization/ASTReaderDecl.cpp
+++ b/lib/Serialization/ASTReaderDecl.cpp
@@ -1463,41 +1463,26 @@ ASTDeclReader::VisitDeclContext(DeclContext *DC) {
 template <typename T>
 ASTDeclReader::RedeclarableResult 
 ASTDeclReader::VisitRedeclarable(Redeclarable<T> *D) {
-  enum RedeclKind { FirstDeclaration = 0, FirstInFile, PointsToPrevious };
-  RedeclKind Kind = (RedeclKind)Record[Idx++];
+  DeclID FirstDeclID = ReadDeclID(Record, Idx);
   
-  DeclID FirstDeclID = 0;
-  switch (Kind) {
-  case FirstDeclaration:
+  // 0 indicates that this declaration was the only declaration of its entity,
+  // and is used for space optimization.
+  if (FirstDeclID == 0)
     FirstDeclID = ThisDeclID;
-    break;
-    
-  case FirstInFile:
-  case PointsToPrevious: {
-    FirstDeclID = ReadDeclID(Record, Idx);
-    DeclID PrevDeclID = ReadDeclID(Record, Idx);
-    
-    T *FirstDecl = cast_or_null<T>(Reader.GetDecl(FirstDeclID));
-    
+  
+  T *FirstDecl = cast_or_null<T>(Reader.GetDecl(FirstDeclID));
+  if (FirstDecl != D) {
     // We delay loading of the redeclaration chain to avoid deeply nested calls.
     // We temporarily set the first (canonical) declaration as the previous one
     // which is the one that matters and mark the real previous DeclID to be
     // loaded & attached later on.
     D->RedeclLink = typename Redeclarable<T>::PreviousDeclLink(FirstDecl);
-    
-    if (Kind == PointsToPrevious) {
-      // Make a note that we need to wire up this declaration to its
-      // previous declaration, later. We don't need to do this for the first
-      // declaration in any given module file, because those will be wired 
-      // together later.
-      Reader.PendingPreviousDecls.push_back(std::make_pair(static_cast<T*>(D),
-                                                           PrevDeclID));
-    }
-    break;
-  }
-  }
-
-  // The result structure takes care of note that we need to load the 
+  }    
+  
+  // Note that this declaration has been deserialized.
+  Reader.RedeclsDeserialized.insert(static_cast<T *>(D));
+                             
+  // The result structure takes care to note that we need to load the 
   // other declaration chains for this ID.
   return RedeclarableResult(Reader, FirstDeclID);
 }
@@ -1529,6 +1514,8 @@ void ASTDeclReader::mergeRedeclarable(Redeclarable<T> *D,
             static_cast<NamespaceDecl *>(static_cast<void*>(ExistingCanon)));
         }
         
+        // FIXME: Update common pointer for RedeclarableTemplateDecls?
+        
         // Don't introduce DCanon into the set of pending declaration chains.
         Redecl.suppress();
         
@@ -1551,7 +1538,7 @@ void ASTDeclReader::mergeRedeclarable(Redeclarable<T> *D,
             Merged.push_back(Redecl.getFirstID());
           
           // If ExistingCanon did not come from a module file, introduce the
-          // first declaration that *does* come from a module file is in the 
+          // first declaration that *does* come from a module file to the 
           // set of pending declaration chains, so that we merge this 
           // declaration.
           if (!ExistingCanon->isFromASTFile() &&
@@ -2140,13 +2127,16 @@ namespace {
   class RedeclChainVisitor {
     ASTReader &Reader;
     SmallVectorImpl<DeclID> &SearchDecls;
+    llvm::SmallPtrSet<Decl *, 16> &Deserialized;
     GlobalDeclID CanonID;
-    llvm::SmallVector<std::pair<Decl *, Decl *>, 4> Chains;
+    llvm::SmallVector<Decl *, 4> Chain;
     
   public:
     RedeclChainVisitor(ASTReader &Reader, SmallVectorImpl<DeclID> &SearchDecls,
+                       llvm::SmallPtrSet<Decl *, 16> &Deserialized,
                        GlobalDeclID CanonID)
-      : Reader(Reader), SearchDecls(SearchDecls), CanonID(CanonID) { }
+      : Reader(Reader), SearchDecls(SearchDecls), Deserialized(Deserialized),
+        CanonID(CanonID) { }
     
     static bool visit(ModuleFile &M, bool Preorder, void *UserData) {
       if (Preorder)
@@ -2155,6 +2145,16 @@ namespace {
       return static_cast<RedeclChainVisitor *>(UserData)->visit(M);
     }
     
+    void addToChain(Decl *D) {
+      if (!D)
+        return;
+      
+      if (Deserialized.count(D)) {
+        Deserialized.erase(D);
+        Chain.push_back(D);
+      }
+    }
+    
     void searchForID(ModuleFile &M, GlobalDeclID GlobalID) {
       // Map global ID of the first declaration down to the local ID
       // used in this module file.
@@ -2165,10 +2165,10 @@ namespace {
       // Perform a binary search to find the local redeclarations for this
       // declaration (if any).
       const LocalRedeclarationsInfo *Result
-        = std::lower_bound(M.RedeclarationsInfo,
-                           M.RedeclarationsInfo + M.LocalNumRedeclarationsInfos, 
+        = std::lower_bound(M.RedeclarationsMap,
+                           M.RedeclarationsMap + M.LocalNumRedeclarationsInMap, 
                            ID, CompareLocalRedeclarationsInfoToID());
-      if (Result == M.RedeclarationsInfo + M.LocalNumRedeclarationsInfos ||
+      if (Result == M.RedeclarationsMap + M.LocalNumRedeclarationsInMap ||
           Result->FirstID != ID) {
         // If we have a previously-canonical singleton declaration that was 
         // merged into another redeclaration chain, create a trivial chain
@@ -2177,21 +2177,18 @@ namespace {
         if (GlobalID != CanonID && 
             GlobalID - NUM_PREDEF_DECL_IDS >= M.BaseDeclID && 
             GlobalID - NUM_PREDEF_DECL_IDS < M.BaseDeclID + M.LocalNumDecls) {
-          if (Decl *D = Reader.GetDecl(GlobalID))
-            Chains.push_back(std::make_pair(D, D));
+          addToChain(Reader.GetDecl(GlobalID));
         }
         
         return;
       }
       
       // Dig out the starting/ending declarations.
-      Decl *FirstLocalDecl = Reader.GetLocalDecl(M, Result->FirstLocalID);
-      Decl *LastLocalDecl = Reader.GetLocalDecl(M, Result->LastLocalID);
-      if (!FirstLocalDecl || !LastLocalDecl)
-        return;
-      
-      // Append this redeclaration chain to the list.
-      Chains.push_back(std::make_pair(FirstLocalDecl, LastLocalDecl));
+      unsigned Offset = Result->Offset;
+      unsigned N = M.RedeclarationChains[Offset];
+      M.RedeclarationChains[Offset++] = 0; // Don't try to deserialize again
+      for (unsigned I = 0; I != N; ++I)
+        addToChain(Reader.GetLocalDecl(M, M.RedeclarationChains[Offset++]));
     }
     
     bool visit(ModuleFile &M) {
@@ -2201,12 +2198,8 @@ namespace {
       return false;
     }
     
-    ArrayRef<std::pair<Decl *, Decl *> > getChains() const {
-      return Chains;
-    }
-    
-    void addParsed(Decl *FirstParsedDecl, Decl *LastParsedDecl) {
-      Chains.push_back(std::make_pair(FirstParsedDecl, LastParsedDecl));
+    ArrayRef<Decl *> getChain() const {
+      return Chain;
     }
   };
 }
@@ -2226,45 +2219,26 @@ void ASTReader::loadPendingDeclChain(serialization::GlobalDeclID ID) {
   if (MergedPos != MergedDecls.end())
     SearchDecls.append(MergedPos->second.begin(), MergedPos->second.end());  
   
-  // Build up the list of redeclaration chains.
-  RedeclChainVisitor Visitor(*this, SearchDecls, CanonID);
+  // Build up the list of redeclarations.
+  RedeclChainVisitor Visitor(*this, SearchDecls, RedeclsDeserialized, CanonID);
   ModuleMgr.visitDepthFirst(&RedeclChainVisitor::visit, &Visitor);
   
   // Retrieve the chains.
-  ArrayRef<std::pair<Decl *, Decl *> > Chains = Visitor.getChains();
-  if (Chains.empty())
+  ArrayRef<Decl *> Chain = Visitor.getChain();
+  if (Chain.empty())
     return;
     
-  // Capture all of the parsed declarations and put them at the end.
+  // Hook up the chains.
   Decl *MostRecent = CanonDecl->getMostRecentDecl();
-  Decl *FirstParsed = MostRecent;
-  if (CanonDecl != MostRecent && !MostRecent->isFromASTFile()) {
-    Decl *Current = MostRecent;
-    while (Decl *Prev = Current->getPreviousDecl()) {
-      if (Prev == CanonDecl)
-        break;
-      
-      if (Prev->isFromASTFile()) {
-        Current = Prev;
-        continue;
-      }
-            
-      // Chain all of the parsed declarations together.
-      ASTDeclReader::attachPreviousDecl(FirstParsed, Prev);
-      FirstParsed = Prev;
-      Current = Prev;
-    }
+  for (unsigned I = 0, N = Chain.size(); I != N; ++I) {
+    if (Chain[I] == CanonDecl)
+      continue;
     
-    Visitor.addParsed(FirstParsed, MostRecent);
+    ASTDeclReader::attachPreviousDecl(Chain[I], MostRecent);
+    MostRecent = Chain[I];
   }
-
-  // Hook up the separate chains.
-  Chains = Visitor.getChains();
-  if (Chains[0].first != CanonDecl)
-    ASTDeclReader::attachPreviousDecl(Chains[0].first, CanonDecl);
-  for (unsigned I = 1, N = Chains.size(); I != N; ++I)
-    ASTDeclReader::attachPreviousDecl(Chains[I].first, Chains[I-1].second);    
-  ASTDeclReader::attachLatestDecl(CanonDecl, Chains.back().second);
+  
+  ASTDeclReader::attachLatestDecl(CanonDecl, MostRecent);  
 }
 
 namespace {
diff --git a/lib/Serialization/ASTWriter.cpp b/lib/Serialization/ASTWriter.cpp
index 2afdc32db0..d49e7110c3 100644
--- a/lib/Serialization/ASTWriter.cpp
+++ b/lib/Serialization/ASTWriter.cpp
@@ -778,7 +778,7 @@ void ASTWriter::WriteBlockInfoBlock() {
   RECORD(IMPORTS);
   RECORD(REFERENCED_SELECTOR_POOL);
   RECORD(TU_UPDATE_LEXICAL);
-  RECORD(LOCAL_REDECLARATIONS);
+  RECORD(LOCAL_REDECLARATIONS_MAP);
   RECORD(SEMA_DECL_REFS);
   RECORD(WEAK_UNDECLARED_IDENTIFIERS);
   RECORD(PENDING_IMPLICIT_INSTANTIATIONS);
@@ -801,7 +801,9 @@ void ASTWriter::WriteBlockInfoBlock() {
   RECORD(OBJC_CHAINED_CATEGORIES);
   RECORD(FILE_SORTED_DECLS);
   RECORD(IMPORTED_MODULES);
-  
+  RECORD(MERGED_DECLARATIONS);
+  RECORD(LOCAL_REDECLARATIONS);
+
   // SourceManager Block.
   BLOCK(SOURCE_MANAGER_BLOCK);
   RECORD(SM_SLOC_FILE_ENTRY);
@@ -2906,6 +2908,73 @@ void ASTWriter::WriteOpenCLExtensions(Sema &SemaRef) {
   Stream.EmitRecord(OPENCL_EXTENSIONS, Record);
 }
 
+void ASTWriter::WriteRedeclarations() {
+  RecordData LocalRedeclChains;
+  SmallVector<serialization::LocalRedeclarationsInfo, 2> LocalRedeclsMap;
+
+  for (unsigned I = 0, N = Redeclarations.size(); I != N; ++I) {
+    Decl *First = Redeclarations[I];
+    assert(First->getPreviousDecl() == 0 && "Not the first declaration?");
+    
+    Decl *MostRecent = First->getMostRecentDecl();
+    
+    // If we only have a single declaration, there is no point in storing
+    // a redeclaration chain.
+    if (First == MostRecent)
+      continue;
+    
+    unsigned Offset = LocalRedeclChains.size();
+    unsigned Size = 0;
+    LocalRedeclChains.push_back(0); // Placeholder for the size.
+    
+    // Collect the set of local redeclarations of this declaration.
+    for (Decl *Prev = MostRecent; Prev != First; 
+         Prev = Prev->getPreviousDecl()) { 
+      if (!Prev->isFromASTFile()) {
+        AddDeclRef(Prev, LocalRedeclChains);
+        ++Size;
+      }
+    }
+    LocalRedeclChains[Offset] = Size;
+    
+    // Reverse the set of local redeclarations, so that we store them in
+    // order (since we found them in reverse order).
+    std::reverse(LocalRedeclChains.end() - Size, LocalRedeclChains.end());
+    
+    // Add the mapping from the first ID to the set of local declarations.
+    LocalRedeclarationsInfo Info = { getDeclID(First), Offset };
+    LocalRedeclsMap.push_back(Info);
+    
+    assert(N == Redeclarations.size() && 
+           "Deserialized a declaration we shouldn't have");
+  }
+  
+  if (LocalRedeclChains.empty())
+    return;
+  
+  // Sort the local redeclarations map by the first declaration ID,
+  // since the reader will be performing binary searches on this information.
+  llvm::array_pod_sort(LocalRedeclsMap.begin(), LocalRedeclsMap.end());
+  
+  // Emit the local redeclarations map.
+  using namespace llvm;
+  llvm::BitCodeAbbrev *Abbrev = new BitCodeAbbrev();
+  Abbrev->Add(BitCodeAbbrevOp(LOCAL_REDECLARATIONS_MAP));
+  Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // # of entries
+  Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
+  unsigned AbbrevID = Stream.EmitAbbrev(Abbrev);
+  
+  RecordData Record;
+  Record.push_back(LOCAL_REDECLARATIONS_MAP);
+  Record.push_back(LocalRedeclsMap.size());
+  Stream.EmitRecordWithBlob(AbbrevID, Record, 
+    reinterpret_cast<char*>(LocalRedeclsMap.data()),
+    LocalRedeclsMap.size() * sizeof(LocalRedeclarationsInfo));
+
+  // Emit the redeclaration chains.
+  Stream.EmitRecord(LOCAL_REDECLARATIONS, LocalRedeclChains);
+}
+
 void ASTWriter::WriteMergedDecls() {
   if (!Chain || Chain->MergedDecls.empty())
     return;
@@ -3424,25 +3493,7 @@ void ASTWriter::WriteASTCore(Sema &SemaRef, MemorizeStatCalls *StatCalls,
   WriteDeclReplacementsBlock();
   WriteChainedObjCCategories();
   WriteMergedDecls();
-  
-  if (!LocalRedeclarations.empty()) {
-    // Sort the local redeclarations info by the first declaration ID,
-    // since the reader will be perforing binary searches on this information.
-    llvm::array_pod_sort(LocalRedeclarations.begin(),LocalRedeclarations.end());
-    
-    llvm::BitCodeAbbrev *Abbrev = new BitCodeAbbrev();
-    Abbrev->Add(BitCodeAbbrevOp(LOCAL_REDECLARATIONS));
-    Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // # of entries
-    Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
-    unsigned AbbrevID = Stream.EmitAbbrev(Abbrev);
-
-    Record.clear();
-    Record.push_back(LOCAL_REDECLARATIONS);
-    Record.push_back(LocalRedeclarations.size());
-    Stream.EmitRecordWithBlob(AbbrevID, Record, 
-      reinterpret_cast<char*>(LocalRedeclarations.data()),
-      LocalRedeclarations.size() * sizeof(LocalRedeclarationsInfo));
-  }
+  WriteRedeclarations();
   
   // Some simple statistics
   Record.clear();
diff --git a/lib/Serialization/ASTWriterDecl.cpp b/lib/Serialization/ASTWriterDecl.cpp
index 02d0c3cfef..0b55d73e45 100644
--- a/lib/Serialization/ASTWriterDecl.cpp
+++ b/lib/Serialization/ASTWriterDecl.cpp
@@ -186,7 +186,7 @@ void ASTDeclWriter::VisitTypedefDecl(TypedefDecl *D) {
   if (!D->hasAttrs() &&
       !D->isImplicit() &&
       !D->isUsed(false) &&
-      !D->getPreviousDecl() &&
+      D->getFirstDeclaration() == D->getMostRecentDecl() &&
       !D->isInvalidDecl() &&
       !D->isReferenced() &&
       !D->isTopLevelDeclInObjCContainer() &&
@@ -236,7 +236,7 @@ void ASTDeclWriter::VisitEnumDecl(EnumDecl *D) {
       !D->isImplicit() &&
       !D->isUsed(false) &&
       !D->hasExtInfo() &&
-      !D->getPreviousDecl() &&
+      D->getFirstDeclaration() == D->getMostRecentDecl() &&
       !D->isInvalidDecl() &&
       !D->isReferenced() &&
       !D->isTopLevelDeclInObjCContainer() &&
@@ -260,7 +260,7 @@ void ASTDeclWriter::VisitRecordDecl(RecordDecl *D) {
       !D->isImplicit() &&
       !D->isUsed(false) &&
       !D->hasExtInfo() &&
-      !D->getPreviousDecl() &&
+      D->getFirstDeclaration() == D->getMostRecentDecl() &&
       !D->isInvalidDecl() &&
       !D->isReferenced() &&
       !D->isTopLevelDeclInObjCContainer() &&
@@ -692,7 +692,7 @@ void ASTDeclWriter::VisitVarDecl(VarDecl *D) {
       !D->isModulePrivate() &&
       D->getDeclName().getNameKind() == DeclarationName::Identifier &&
       !D->hasExtInfo() &&
-      !D->getPreviousDecl() &&
+      D->getFirstDeclaration() == D->getMostRecentDecl() &&
       !D->hasCXXDirectInitializer() &&
       D->getInit() == 0 &&
       !isa<ParmVarDecl>(D) &&
@@ -1237,27 +1237,23 @@ void ASTDeclWriter::VisitDeclContext(DeclContext *DC, uint64_t LexicalOffset,
 
 template <typename T>
 void ASTDeclWriter::VisitRedeclarable(Redeclarable<T> *D) {
-  enum { FirstDeclaration = 0, FirstInFile, PointsToPrevious };
-  T *Prev = D->getPreviousDecl();
   T *First = D->getFirstDeclaration();
-  
-  if (!Prev) {
-    Record.push_back(FirstDeclaration);
-  } else {  
-    Record.push_back(Prev->isFromASTFile()? FirstInFile : PointsToPrevious);
+  if (First->getMostRecentDecl() != First) {
+    // There is more than one declaration of this entity, so we will need to 
+    // write a redeclaration chain.
     Writer.AddDeclRef(First, Record);
-    Writer.AddDeclRef(D->getPreviousDecl(), Record);
+    Writer.Redeclarations.insert(First);
+
+    // Make sure that we serialize both the previous and the most-recent 
+    // declarations, which (transitively) ensures that all declarations in the
+    // chain get serialized.
+    (void)Writer.GetDeclRef(D->getPreviousDecl());
+    (void)Writer.GetDeclRef(First->getMostRecentDecl());
+  } else {
+    // We use the sentinel value 0 to indicate an only declaration.
+    Record.push_back(0);
   }
   
-  if (D->RedeclLink.getPointer() != D && (!Prev || Prev->isFromASTFile())) {
-    // Capture the set of redeclarations in this file.
-    LocalRedeclarationsInfo LocalInfo = {
-      Writer.GetDeclRef(First),
-      Writer.GetDeclRef(static_cast<T*>(D)),
-      Writer.GetDeclRef(D->getMostRecentDecl())
-    };
-    Writer.LocalRedeclarations.push_back(LocalInfo);    
-  }
 }
 
 //===----------------------------------------------------------------------===//
diff --git a/lib/Serialization/Module.cpp b/lib/Serialization/Module.cpp
index 7db3accd55..cb8c9cca06 100644
--- a/lib/Serialization/Module.cpp
+++ b/lib/Serialization/Module.cpp
@@ -35,7 +35,7 @@ ModuleFile::ModuleFile(ModuleKind Kind)
     SelectorLookupTableData(0), SelectorLookupTable(0), LocalNumDecls(0),
     DeclOffsets(0), BaseDeclID(0),
     LocalNumCXXBaseSpecifiers(0), CXXBaseSpecifiersOffsets(0),
-    FileSortedDecls(0), RedeclarationsInfo(0), LocalNumRedeclarationsInfos(0),
+    FileSortedDecls(0), RedeclarationsMap(0), LocalNumRedeclarationsInMap(0),
     LocalNumTypes(0), TypeOffsets(0), BaseTypeIndex(0), StatCache(0)
 {}