[clang][deps] Ensure deterministic order of TU '-fmodule-file=' arguments

[jansvoboda11]

Summary

Translation units with multiple direct modular dependencies trigger a non-deterministic ordering in clang-scan-deps. This boils down to usage of std::unordered_map, which gets replaced by std::map in this patch.

Depends on D103526.

[tschuett]

llvm discourages the use of std::map:
https://llvm.org/docs/ProgrammersManual.html#map

[dexonsmith]

I'm not sure the performance problems with std::map will matter in practice here, but have you considered sorting before emission rather than relying on the data structure's iteration order? (It'd make it easy to switch to StringMap in the future.)

[jansvoboda11]

I'm aware of the drawbacks of std::map, but I think having the container sorted at all times promotes correctness/determinism which we really care about in this context. Forgetting to call sort at all the right places is very easy as this patch demonstrates.

But if you are strongly opposed to using std::map here, I'm okay with using std::unordered_map or llvm::StringMap and sorting where necessary.

[dexonsmith]

Another option to be aware of is MapVector (https://llvm.org/docs/ProgrammersManual.html#llvm-adt-mapvector-h). Does not sort, but guarantees iteration order.

But LGTM anyway. I don't think the exact data structure is important here. Please just add a comment documenting that consumers need a deterministic iteration order so anyone updating or optimizing this later knows what the constraints are.

clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp

FullDependenciesResult getFullDependencies() const {
 
       FDR.FullDeps = std::move(FD);
       return FDR;
     }
 
   private:
     std::vector<std::string> Dependencies;
     std::vector<PrebuiltModuleDep> PrebuiltModuleDeps;
-    std::unordered_map<std::string, ModuleDeps> ClangModuleDeps;
+    std::map<std::string, ModuleDeps> ClangModuleDeps;
     std::string ContextHash;
     std::vector<std::string> OutputPaths;
     const llvm::StringSet<> &AlreadySeen;
   };
 
   // We expect a single command here because if a source file occurs multiple
   // times in the original CDB, then `computeDependencies` would run the
   // `DependencyScanningAction` once for every time the input occured in the

clang/test/ClangScanDeps/modules-pch.c

 // CHECK-PCH-NEXT:         {
 // CHECK-PCH-NEXT:           "context-hash": "[[HASH_MOD_PCH]]",
 // CHECK-PCH-NEXT:           "module-name": "ModPCH"
 // CHECK-PCH-NEXT:         }
 // CHECK-PCH-NEXT:       ],
 // CHECK-PCH-NEXT:       "command-line": [
 // CHECK-PCH-NEXT:         "-fno-implicit-modules",
 // CHECK-PCH-NEXT:         "-fno-implicit-module-maps",
-// CHECK-PCH-DAG:          "-fmodule-file=[[PREFIX]]/build/[[HASH_MOD_COMMON_1]]/ModCommon1-{{.*}}.pcm",
-// CHECK-PCH-DAG:          "-fmodule-file=[[PREFIX]]/build/[[HASH_MOD_COMMON_2]]/ModCommon2-{{.*}}.pcm",
-// CHECK-PCH-DAG:          "-fmodule-file=[[PREFIX]]/build/[[HASH_MOD_PCH]]/ModPCH-{{.*}}.pcm",
+// CHECK-PCH-NEXT:         "-fmodule-file=[[PREFIX]]/build/[[HASH_MOD_COMMON_1]]/ModCommon1-{{.*}}.pcm",
+// CHECK-PCH-NEXT:         "-fmodule-file=[[PREFIX]]/build/[[HASH_MOD_COMMON_2]]/ModCommon2-{{.*}}.pcm",
+// CHECK-PCH-NEXT:         "-fmodule-file=[[PREFIX]]/build/[[HASH_MOD_PCH]]/ModPCH-{{.*}}.pcm",
 // CHECK-PCH-NEXT:         "-fmodule-map-file=[[PREFIX]]/module.modulemap",
 // CHECK-PCH-NEXT:         "-fmodule-map-file=[[PREFIX]]/module.modulemap",
 // CHECK-PCH-NEXT:         "-fmodule-map-file=[[PREFIX]]/module.modulemap"
 // CHECK-PCH-NEXT:       ],
 // CHECK-PCH-NEXT:       "file-deps": [
 // CHECK-PCH-NEXT:         "[[PREFIX]]/pch.h"
 // CHECK-PCH-NEXT:       ],
 // CHECK-PCH-NEXT:       "input-file": "[[PREFIX]]/pch.h"