[Modules] Make the AST serialization always use lexicographic order when

traversing the identifier table.

No easy test case as this table is somewhere between hard and impossible
to observe as non-deterministically ordered. The table is a hash table
but we hash the string contents and never remove entries from the table
so the growth pattern, etc, is all completely fixed. However, relying on
the hash function being deterministic is specifically against the
long-term direction of LLVM's hashing datastructures, which are intended
to provide *no* ordering guarantees. As such, this defends against these
things by sorting the identifiers. Sorting identifiers right before we
emit them to a serialized form seems a low cost for predictability here.

llvm-svn: 233332

1 files changed, 12 insertions, 4 deletions

diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp
index 3f2c46d80ef..655c9fd28b5 100644
--- a/clang/lib/Serialization/ASTWriter.cpp
+++ b/clang/lib/Serialization/ASTWriter.cpp
@@ -3504,10 +3504,16 @@ void ASTWriter::WriteIdentifierTable(Preprocessor &PP,
     // table to enable checking of the predefines buffer in the case
     // where the user adds new macro definitions when building the AST
     // file.
+    SmallVector<const IdentifierInfo *, 128> IIs;
     for (IdentifierTable::iterator ID = PP.getIdentifierTable().begin(),
                                 IDEnd = PP.getIdentifierTable().end();
          ID != IDEnd; ++ID)
-      getIdentifierRef(ID->second);
+      IIs.push_back(ID->second);
+    // Sort the identifiers lexicographically before getting them references so
+    // that their order is stable.
+    std::sort(IIs.begin(), IIs.end(), llvm::less_ptr<IdentifierInfo>());
+    for (const IdentifierInfo *II : IIs)
+      getIdentifierRef(II);
 
     // Create the on-disk hash table representation. We only store offsets
     // for identifiers that appear here for the first time.
@@ -4504,15 +4510,17 @@ void ASTWriter::WriteASTCore(Sema &SemaRef,
 
   // Make sure all decls associated with an identifier are registered for
   // serialization.
-  llvm::SmallVector<const IdentifierInfo*, 256> IIsToVisit;
+  llvm::SmallVector<const IdentifierInfo*, 256> IIs;
   for (IdentifierTable::iterator ID = PP.getIdentifierTable().begin(),
                               IDEnd = PP.getIdentifierTable().end();
        ID != IDEnd; ++ID) {
     const IdentifierInfo *II = ID->second;
     if (!Chain || !II->isFromAST() || II->hasChangedSinceDeserialization())
-      IIsToVisit.push_back(II);
+      IIs.push_back(II);
   }
-  for (const IdentifierInfo *II : IIsToVisit) {
+  // Sort the identifiers to visit based on their name.
+  std::sort(IIs.begin(), IIs.end(), llvm::less_ptr<IdentifierInfo>());
+  for (const IdentifierInfo *II : IIs) {
     for (IdentifierResolver::iterator D = SemaRef.IdResolver.begin(II),
                                    DEnd = SemaRef.IdResolver.end();
          D != DEnd; ++D) {