[Modules] When writing out the on-disk hash table for the decl context

lookup tables, we need to establish a stable ordering for constructing
the hash table. This is trickier than it might seem.

Most of these cases are easily handled by sorting the lookup results
associated with a specific name that has an identifier. However for
constructors and conversion functions, the story is more complicated.
Here we need to merge all of the constructors or conversion functions
together and this merge needs to be stable. We don't have any stable
ordering for either constructors or conversion functions as both would
require a stable ordering across types.

Instead, when we have constructors or conversion functions in the
results, we reconstruct a stable order by walking the decl context in
lexical order and merging them in the order their particular declaration
names are encountered. This doesn't generalize as there might be found
declaration names which don't actually occur within the lexical context,
but for constructors and conversion functions it is safe. It does
require loading the entire decl context if necessary to establish the
ordering but there doesn't seem to be a meaningful way around that.

Many thanks to Richard for talking through all of the design choices
here. While I wrote the code, he guided all the actual decisions about
how to establish the order of things.

No test case yet because the test case I have doesn't pass yet -- there
are still more sources of non-determinism. However, this is complex
enough that I wanted it to go into its own commit in case it causes some
unforseen issue or needs to be reverted.

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

1 files changed, 90 insertions, 15 deletions

diff --git a/lib/Serialization/ASTWriter.cpp b/lib/Serialization/ASTWriter.cpp
index 5b8d8b7d0e..a17b310a95 100644
--- a/lib/Serialization/ASTWriter.cpp
+++ b/lib/Serialization/ASTWriter.cpp
@@ -3761,15 +3761,34 @@ ASTWriter::GenerateNameLookupTable(const DeclContext *DC,
          !DC->HasLazyExternalLexicalLookups &&
          "must call buildLookups first");
 
+  // Create the on-disk hash table representation.
   llvm::OnDiskChainedHashTableGenerator<ASTDeclContextNameLookupTrait>
       Generator;
   ASTDeclContextNameLookupTrait Trait(*this);
 
-  // Create the on-disk hash table representation.
+  // Store the sortable lookup results -- IE, those with meaningful names. We
+  // will sort them by the DeclarationName in order to stabilize the ordering
+  // of the hash table. We can't do this for constructors or conversion
+  // functions which are handled separately.
+  SmallVector<std::pair<DeclarationName, DeclContext::lookup_result>, 16>
+      NamedResults;
+
+  // We can't directly construct a nonce constructor or conversion name without
+  // tripping asserts, so we just recall the first one we see. Only the kind
+  // will actually be serialized.
   DeclarationName ConstructorName;
   DeclarationName ConversionName;
-  SmallVector<NamedDecl *, 8> ConstructorDecls;
-  SmallVector<NamedDecl *, 4> ConversionDecls;
+  // Retain a mapping from each actual declaration name to the results
+  // associated with it. We use a map here because the order in which we
+  // discover these lookup results isn't ordered. We have to re-establish
+  // a stable ordering which we do by walking the children of the decl context,
+  // and emitting these in the order in which their names first appeared. Note
+  // that the names' first appearance may not be one of the results or a result
+  // at all. We just use this to establish an ordering.
+  llvm::SmallDenseMap<DeclarationName, DeclContext::lookup_result, 8>
+      ConstructorResults;
+  llvm::SmallDenseMap<DeclarationName, DeclContext::lookup_result, 4>
+      ConversionResults;
 
   visitLocalLookupResults(DC, [&](DeclarationName Name,
                                   DeclContext::lookup_result Result) {
@@ -3786,34 +3805,90 @@ ASTWriter::GenerateNameLookupTable(const DeclContext *DC,
       // has the DeclarationName of the inherited constructors.
       if (!ConstructorName)
         ConstructorName = Name;
-      ConstructorDecls.append(Result.begin(), Result.end());
+      ConstructorResults.insert(std::make_pair(Name, Result));
       return;
 
     case DeclarationName::CXXConversionFunctionName:
       if (!ConversionName)
         ConversionName = Name;
-      ConversionDecls.append(Result.begin(), Result.end());
+      ConversionResults.insert(std::make_pair(Name, Result));
       return;
 
     default:
-      break;
+      NamedResults.push_back(std::make_pair(Name, Result));
     }
 
-    Generator.insert(Name, Result, Trait);
   });
 
-  // Add the constructors.
-  if (!ConstructorDecls.empty()) {
+  // Sort and emit the named results first. This is the easy case.
+  std::sort(
+      NamedResults.begin(), NamedResults.end(),
+      [](const std::pair<DeclarationName, DeclContext::lookup_result> &LHS,
+         const std::pair<DeclarationName, DeclContext::lookup_result> &RHS) {
+        return LHS.first < RHS.first;
+      });
+  for (auto Results : NamedResults)
+    Generator.insert(Results.first, Results.second, Trait);
+
+  // We have to specially handle the constructor and conversion function
+  // declarations found.
+  if (ConstructorResults.size() == 1) {
+    // A special case that is easy is when we have just one constructor
+    // declaration name.
     Generator.insert(ConstructorName,
-                     DeclContext::lookup_result(ConstructorDecls),
+                     ConstructorResults.lookup(ConstructorName), Trait);
+    ConstructorResults.clear();
+  }
+  if (ConversionResults.size() == 1) {
+    // A special case that is easy is when we have just one conversion function
+    // declaration name.
+    Generator.insert(ConversionName, ConversionResults.lookup(ConversionName),
                      Trait);
+    ConversionResults.clear();
   }
+  if (!ConstructorResults.empty() || !ConversionResults.empty()) {
+    SmallVector<NamedDecl *, 8> ConstructorDecls;
+    SmallVector<NamedDecl *, 8> ConversionDecls;
+
+    // Walk the decls in the context and collapse the results in that order. We
+    // handle both constructors and conversion functions in a single walk as
+    // the walk is a relative cache-hostile linked list walk.
+    for (Decl *ChildD : DC->decls())
+      if (auto *ChildND = dyn_cast<NamedDecl>(ChildD)) {
+        auto ConstructorResultsIt =
+            ConstructorResults.find(ChildND->getDeclName());
+        if (ConstructorResultsIt != ConstructorResults.end()) {
+          ConstructorDecls.append(ConstructorResultsIt->second.begin(),
+                                  ConstructorResultsIt->second.end());
+          ConstructorResults.erase(ConstructorResultsIt);
+        }
 
-  // Add the conversion functions.
-  if (!ConversionDecls.empty()) {
-    Generator.insert(ConversionName,
-                     DeclContext::lookup_result(ConversionDecls),
-                     Trait);
+        auto ConversionResultsIt =
+            ConversionResults.find(ChildND->getDeclName());
+        if (ConversionResultsIt != ConversionResults.end()) {
+          ConversionDecls.append(ConversionResultsIt->second.begin(),
+                                 ConversionResultsIt->second.end());
+          ConversionResults.erase(ConversionResultsIt);
+        }
+
+        // If we handle all of the results, we're done.
+        if (ConstructorResults.empty() && ConversionResults.empty())
+          break;
+      }
+    assert(ConstructorResults.empty() && "Have constructor lookup results not "
+                                         "associated with a declaration name "
+                                         "within the context!");
+    assert(ConversionResults.empty() && "Have conversion function lookup "
+                                        "results not associated with a "
+                                        "declaration name within the context!");
+
+    if (!ConstructorDecls.empty())
+      Generator.insert(ConstructorName,
+                       DeclContext::lookup_result(ConstructorDecls), Trait);
+
+    if (!ConversionDecls.empty())
+      Generator.insert(ConversionName,
+                       DeclContext::lookup_result(ConversionDecls), Trait);
   }
 
   // Create the on-disk hash table in a buffer.