[clang][deps] Make order of module dependencies deterministic

[benlangmuir]

Summary

This fixes the underlying module dependencies, which had a non-deterministic order, which was also visible in the order of calls to DependencyConsumer methods. This was not directly observable in the clang-scan-deps utility, because it was previously seeing a sorted order from std::map in DependencyScanningTool. However, the underlying API previously created a likely issue for any other clients. Note: if you only apply the change from DependencyScanningTool, you can see the issue in clang-scan-deps, and existing tests will fail non-deterministicaly.

[jansvoboda11]

clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp

179

What's the reason for wrapping ModuleDeps in unique_ptr?

[benlangmuir]

clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp

179

Oh hmm, my thinking was that DenseMap is optimized for small values, but I guess in this setup the map only stores integers and the values are in a vector. I'll change this to values, thanks!

[benlangmuir]

Removed use of std::unique_ptr in DependencyScanningTool.cpp, per review feedback.

@jansvoboda11 Note: there is another map containing std::unique_ptr<ModuleDeps> in ModuleDepCollector, but that one is required for correctness. The problem is that there is code that forms a ModuleDeps & lvalue and assumes it will be correct after mutating the containing ModularDeps map. For example, the signature of addAllSubmoduleDeps requires this. If we want to switch to using this as a value in the map, we would need to do the lookup in the map again after each mutation. This code worked previously with unordered_map, because it guarantees that keys and values are not mutated by unrelated mutations of the containing map, unlike MapVector. In practice, this means there is no additional overhead from the unique_ptr, because it was already doing a separate allocation for each value in the unordered_map.

[jansvoboda11]

Thanks for explaining this, LGTM.

clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h

void moduleImport(SourceLocation ImportLoc, ModuleIdPath Path,
                     const Module *Imported) override;
 
   void EndOfMainFile() override;
 
 private:
   /// The parent dependency collector.
   ModuleDepCollector &MDC;
   /// Working set of direct modular dependencies.
-  llvm::DenseSet<const Module *> DirectModularDeps;
+  llvm::SetVector<const Module *> DirectModularDeps;
   /// Working set of direct modular dependencies that have already been built.
-  llvm::DenseSet<const Module *> DirectPrebuiltModularDeps;
+  llvm::SetVector<const Module *> DirectPrebuiltModularDeps;
 
   void handleImport(const Module *Imported);
 
   /// Adds direct modular dependencies that have already been built to the
   /// ModuleDeps instance.
   void
   addAllSubmodulePrebuiltDeps(const Module *M, ModuleDeps &MD,
                               llvm::DenseSet<const Module *> &SeenSubmodules);
private:
   /// Path to the main source file.
   std::string MainFile;
   /// Hash identifying the compilation conditions of the current TU.
   std::string ContextHash;
   /// Non-modular file dependencies. This includes the main source file and
   /// textually included header files.
   std::vector<std::string> FileDeps;
   /// Direct and transitive modular dependencies of the main source file.
-  std::unordered_map<const Module *, ModuleDeps> ModularDeps;
+  llvm::MapVector<const Module *, std::unique_ptr<ModuleDeps>> ModularDeps;
   /// Options that control the dependency output generation.
   std::unique_ptr<DependencyOutputOptions> Opts;
   /// The original Clang invocation passed to dependency scanner.
   CompilerInvocation OriginalInvocation;
   /// Whether to optimize the modules' command-line arguments.
   bool OptimizeArgs;
 
   /// Checks whether the module is known as being prebuilt.

clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp

FullDependenciesResult getFullDependencies(
 
       FDR.FullDeps = std::move(FD);
       return FDR;
     }
 
   private:
     std::vector<std::string> Dependencies;
     std::vector<PrebuiltModuleDep> PrebuiltModuleDeps;
-    std::map<std::string, ModuleDeps> ClangModuleDeps;
+    llvm::MapVector<std::string, ModuleDeps, llvm::StringMap<unsigned>> ClangModuleDeps;
     std::string ContextHash;
     std::vector<std::string> OutputPaths;
     const llvm::StringSet<> &AlreadySeen;
   };
 
   FullDependencyPrinterConsumer Consumer(AlreadySeen);
   llvm::Error Result =
       Worker.computeDependencies(CWD, CommandLine, Consumer, ModuleName);
   if (Result)
     return std::move(Result);
   return Consumer.getFullDependencies(CommandLine);
 }
 
 } // end namespace dependencies
 } // end namespace tooling
 } // end namespace clang

clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp

for (const Module *M : DirectModularDeps) {
     if (!M->getASTFile())
       continue;
     handleTopLevelModule(M);
   }
 
   MDC.Consumer.handleDependencyOutputOpts(*MDC.Opts);
 
   for (auto &&I : MDC.ModularDeps)
-    MDC.Consumer.handleModuleDependency(I.second);
+    MDC.Consumer.handleModuleDependency(*I.second);
 
   for (auto &&I : MDC.FileDeps)
     MDC.Consumer.handleFileDependency(I);
 
   for (auto &&I : DirectPrebuiltModularDeps)
     MDC.Consumer.handlePrebuiltModuleDependency(PrebuiltModuleDep{I});
 }
 
 ModuleID ModuleDepCollectorPP::handleTopLevelModule(const Module *M) {
   assert(M == M->getTopLevelModule() && "Expected top level module!");
 
   // If this module has been handled already, just return its ID.
-  auto ModI = MDC.ModularDeps.insert({M, ModuleDeps{}});
+  auto ModI = MDC.ModularDeps.insert({M, nullptr});
   if (!ModI.second)
-    return ModI.first->second.ID;
+    return ModI.first->second->ID;
 
-  ModuleDeps &MD = ModI.first->second;
+  ModI.first->second = std::make_unique<ModuleDeps>();
+  ModuleDeps &MD = *ModI.first->second;
 
   MD.ID.ModuleName = M->getFullModuleName();
   MD.ImportedByMainFile = DirectModularDeps.contains(M);
   MD.ImplicitModulePCMPath = std::string(M->getASTFile()->getName());
   MD.IsSystem = M->IsSystem;
 
   const FileEntry *ModuleMap = MDC.ScanInstance.getPreprocessor()
                                    .getHeaderSearchInfo()