This revision was landed with ongoing or failed builds. This revision was automatically updated to reflect the committed changes. Closed by commit rG6b80f00bac6a: [clang][deps] NFC: Refactor and comment ModuleDeps sorting (authored by jansvoboda11).
Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D145197/new/ https://reviews.llvm.org/D145197 Files: clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h clang/tools/clang-scan-deps/ClangScanDeps.cpp
Index: clang/tools/clang-scan-deps/ClangScanDeps.cpp =================================================================== --- clang/tools/clang-scan-deps/ClangScanDeps.cpp +++ clang/tools/clang-scan-deps/ClangScanDeps.cpp @@ -323,11 +323,10 @@ 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) @@ -406,11 +405,7 @@ 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; @@ -470,20 +465,37 @@ 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; - return hash_combine(IMID.ID.ModuleName, IMID.ID.ContextHash); + 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); } + + struct Hasher { + std::size_t operator()(const IndexedModuleID &IMID) const { + return llvm::hash_combine(IMID.ID.ModuleName, IMID.ID.ContextHash); + } + }; }; struct InputDeps { @@ -496,7 +508,7 @@ }; std::mutex Lock; - std::unordered_map<IndexedModuleID, ModuleDeps, IndexedModuleIDHasher> + std::unordered_map<IndexedModuleID, ModuleDeps, IndexedModuleID::Hasher> Modules; std::vector<InputDeps> Inputs; }; Index: clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h =================================================================== --- clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h +++ clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h @@ -59,7 +59,13 @@ 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); } };
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits