[clang][deps] NFC: Refactor and comment ModuleDeps sorting

[jansvoboda11]

Summary

I once again stumbled across IndexedModuleID and was confused by the mutable InputIndex field.

This patch adds comments around that piece of code and unifies/simplifies related functions.

[Bigcheese]

lgtm

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

struct ModuleID {
   /// Modules with the same name and ContextHash but different invocations could
   /// cause non-deterministic build results.
   ///
   /// Modules with the same name but a different \c ContextHash should be
   /// treated as separate modules for the purpose of a build.
   std::string ContextHash;
 
   bool operator==(const ModuleID &Other) const {
-    return ModuleName == Other.ModuleName && ContextHash == Other.ContextHash;
+    return std::tie(ModuleName, ContextHash) ==
+           std::tie(Other.ModuleName, Other.ContextHash);
+  }
+
+  bool operator<(const ModuleID& Other) const {
+    return std::tie(ModuleName, ContextHash) <
+           std::tie(Other.ModuleName, Other.ContextHash);
   }
 };
 
 /// P1689ModuleInfo - Represents the needed information of standard C++20
 /// modules for P1689 format.
 struct P1689ModuleInfo {
   /// The name of the module. This may include `:` for partitions.
   std::string ModuleName;

clang/tools/clang-scan-deps/ClangScanDeps.cpp

 static llvm::json::Array toJSONSorted(const llvm::StringSet<> &Set) {
   std::vector<llvm::StringRef> Strings;
   for (auto &&I : Set)
     Strings.push_back(I.getKey());
   llvm::sort(Strings);
   return llvm::json::Array(Strings);
 }
 
+// Technically, we don't need to sort the dependency list to get determinism.
+// Leaving these be will simply preserve the import order.
 static llvm::json::Array toJSONSorted(std::vector<ModuleID> V) {
-  llvm::sort(V, [](const ModuleID &A, const ModuleID &B) {
-    return std::tie(A.ModuleName, A.ContextHash) <
-           std::tie(B.ModuleName, B.ContextHash);
-  });
+  llvm::sort(V);
 
   llvm::json::Array Ret;
   for (const ModuleID &MID : V)
     Ret.push_back(llvm::json::Object(
         {{"module-name", MID.ModuleName}, {"context-hash", MID.ContextHash}}));
   return Ret;
 }
 
bool roundTripCommands(raw_ostream &ErrOS) {
     return false;
   }
 
   void printFullOutput(raw_ostream &OS) {
     // Sort the modules by name to get a deterministic order.
     std::vector<IndexedModuleID> ModuleIDs;
     for (auto &&M : Modules)
       ModuleIDs.push_back(M.first);
-    llvm::sort(ModuleIDs,
-               [](const IndexedModuleID &A, const IndexedModuleID &B) {
-                 return std::tie(A.ID.ModuleName, A.InputIndex) <
-                        std::tie(B.ID.ModuleName, B.InputIndex);
-               });
+    llvm::sort(ModuleIDs);
 
     using namespace llvm::json;
 
     Array OutModules;
     for (auto &&ModID : ModuleIDs) {
       auto &MD = Modules[ModID];
       Object O{
           {"name", MD.ID.ModuleName},
void printFullOutput(raw_ostream &OS) {
     };
 
     OS << llvm::formatv("{0:2}\n", Value(std::move(Output)));
   }
 
 private:
   struct IndexedModuleID {
     ModuleID ID;
+
+    // FIXME: This is mutable so that it can still be updated after insertion
+    //  into an unordered associative container. This is "fine", since this
+    //  field doesn't contribute to the hash, but it's a brittle hack.
     mutable size_t InputIndex;
 
     bool operator==(const IndexedModuleID &Other) const {
-      return ID.ModuleName == Other.ID.ModuleName &&
-             ID.ContextHash == Other.ID.ContextHash;
+      return std::tie(ID.ModuleName, ID.ContextHash) ==
+             std::tie(Other.ID.ModuleName, Other.ID.ContextHash);
     }
-  };
 
-  struct IndexedModuleIDHasher {
-    std::size_t operator()(const IndexedModuleID &IMID) const {
-      using llvm::hash_combine;
+    bool operator<(const IndexedModuleID &Other) const {
+      /// We need the output of clang-scan-deps to be deterministic. However,
+      /// the dependency graph may contain two modules with the same name. How
+      /// do we decide which one to print first? If we made that decision based
+      /// on the context hash, the ordering would be deterministic, but
+      /// different across machines. This can happen for example when the inputs
+      /// or the SDKs (which both contribute to the "context" hash) live in
+      /// different absolute locations. We solve that by tracking the index of
+      /// the first input TU that (transitively) imports the dependency, which
+      /// is always the same for the same input, resulting in deterministic
+      /// sorting that's also reproducible across machines.
+      return std::tie(ID.ModuleName, InputIndex) <
+             std::tie(Other.ID.ModuleName, Other.InputIndex);
+    }
 
-      return hash_combine(IMID.ID.ModuleName, IMID.ID.ContextHash);
+    struct Hasher {
+      std::size_t operator()(const IndexedModuleID &IMID) const {
+        return llvm::hash_combine(IMID.ID.ModuleName, IMID.ID.ContextHash);
       }
     };
+  };
 
   struct InputDeps {
     std::string FileName;
     std::string ContextHash;
     std::vector<std::string> FileDeps;
     std::vector<ModuleID> ModuleDeps;
     std::vector<std::string> DriverCommandLine;
     std::vector<Command> Commands;
   };
 
   std::mutex Lock;
-  std::unordered_map<IndexedModuleID, ModuleDeps, IndexedModuleIDHasher>
+  std::unordered_map<IndexedModuleID, ModuleDeps, IndexedModuleID::Hasher>
       Modules;
   std::vector<InputDeps> Inputs;
 };
 
 static bool handleTranslationUnitResult(
     StringRef Input, llvm::Expected<TranslationUnitDeps> &MaybeTUDeps,
     FullDeps &FD, size_t InputIndex, SharedStream &OS, SharedStream &Errs) {
   if (!MaybeTUDeps) {