[clang][deps] Preserve input ordering in the full output

[jansvoboda11]

Summary

This patch makes sure the ordering of TUs in the input CDB is preserved in the full output. Previously, the results were pushed into a global vector, potentially out-of-order and then sorted by the input file name. This is
non-deterministic when the CDB contains multiple entries with the same input file. This patch fixes that by pre-allocating the output vector and instead of appending, writes to the index corresponding to the current input. This also
eliminates one critical section.

[benlangmuir]

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

291–293

Since the input index is coming from "outside": does this operator[] assert if the index is out of range? If not, we should do so here. I would also suggest asserting the value isn't already populated (e.g. assert(ID.FileName.empty())).

790

Since you should never resize FullDeps after you start, how about removing resize and instead:

• Make FullDeps constructor take the size
• Change FullDeps FD; to std::optional<FullDeps>
• Change this line to FullDeps.emplace(Inputs.size())

[jansvoboda11]

Add asserts, make FullDeps take NumInputs in the constructor.

[jansvoboda11]

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

790

We don't want to resize when we're only scanning by module name, in that case our input is not a translation unit. I implemented your idea and will try to improve how we model the result types in a follow-up.

[Jake-Egan]

Hi, this new test fails on AIX, could you take a look please?
https://lab.llvm.org/buildbot/#/builders/214/builds/6148/steps/6/logs/FAIL__Clang__modules-full-output-tu-order_c

[jansvoboda11]

In D145098#4167163, @Jake-Egan wrote:

Hi, this new test fails on AIX, could you take a look please?
https://lab.llvm.org/buildbot/#/builders/214/builds/6148/steps/6/logs/FAIL__Clang__modules-full-output-tu-order_c

-fno-integrated-as strikes again. Thanks for reporting this, should be fixed in 3ac8d32.

[Jake-Egan]

Thanks for addressing this. Unfortunately the test is still failing after the fix and a clean build

https://lab.llvm.org/buildbot/#/builders/214/builds/6170/steps/6/logs/FAIL__Clang__modules-full-output-tu-order_c

clang/test/ClangScanDeps/modules-full-output-tu-order.c

+// This test checks that ordering of TUs in the input CDB is preserved in the full output.
+
+// RUN: rm -rf %t
+// RUN: split-file %s %t
+
+//--- cdb.json.template
+[
+  {
+    "directory": "DIR",
+    "file": "DIR/tu.c",
+    "command": "clang -fmodules -fmodules-cache-path=DIR/cache -c DIR/tu.c -o DIR/tu1.o"
+  },
+  {
+    "directory": "DIR",
+    "file": "DIR/tu.c",
+    "command": "clang -fmodules -fmodules-cache-path=DIR/cache -c DIR/tu.c -o DIR/tu2.o"
+  }
+]
+
+//--- tu.c
+
+// RUN: sed "s|DIR|%/t|g" %t/cdb.json.template > %t/cdb.json
+// RUN: clang-scan-deps -compilation-database %t/cdb.json -format experimental-full > %t/result.json
+// RUN: cat %t/result.json | sed 's:\\\\\?:/:g' | FileCheck -DPREFIX=%/t %s
+
+// CHECK:      {
+// CHECK-NEXT:   "modules": [],
+// CHECK-NEXT:   "translation-units": [
+// CHECK-NEXT:     {
+// CHECK-NEXT:       "commands": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "clang-context-hash": "{{.*}}",
+// CHECK-NEXT:           "clang-module-deps": [],
+// CHECK-NEXT:           "command-line": [
+// CHECK:                  "-o",
+// CHECK-NEXT:             "[[PREFIX]]/tu1.o",
+// CHECK:                ],
+// CHECK-NEXT:           "executable": "clang",
+// CHECK-NEXT:           "file-deps": [
+// CHECK-NEXT:             "[[PREFIX]]/tu.c"
+// CHECK-NEXT:           ],
+// CHECK-NEXT:           "input-file": "[[PREFIX]]/tu.c"
+// CHECK-NEXT:         }
+// CHECK:            ]
+// CHECK-NEXT:     },
+// CHECK-NEXT:     {
+// CHECK-NEXT:       "commands": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "clang-context-hash": "{{.*}}",
+// CHECK-NEXT:           "clang-module-deps": [],
+// CHECK-NEXT:           "command-line": [
+// CHECK:                  "-o",
+// CHECK-NEXT:             "[[PREFIX]]/tu2.o",
+// CHECK:                ],
+// CHECK-NEXT:           "executable": "clang",
+// CHECK-NEXT:           "file-deps": [
+// CHECK-NEXT:             "[[PREFIX]]/tu.c"
+// CHECK-NEXT:           ],
+// CHECK-NEXT:           "input-file": "[[PREFIX]]/tu.c"
+// CHECK-NEXT:         }
+// CHECK:            ]
+// CHECK-NEXT:     }
+// CHECK-NEXT:   ]
+// CHECK-NEXT: }

clang/test/ClangScanDeps/modules-full.cpp

 // CHECK-NEXT:       ],
 // CHECK-NEXT:       "name": "header2"
 // CHECK-NEXT:     }
 // CHECK-NEXT:   ],
 // CHECK-NEXT:   "translation-units": [
 // CHECK-NEXT:     {
 // CHECK-NEXT:       "commands": [
 // CHECK-NEXT:         {
-// CHECK-NEXT:           "clang-context-hash": "[[HASH_TU:[A-Z0-9]+]]",
+// CHECK-NEXT:           "clang-context-hash": "[[HASH_TU_DINCLUDE:[A-Z0-9]+]]",
 // CHECK-NEXT:           "clang-module-deps": [
 // CHECK-NEXT:             {
-// CHECK-NEXT:               "context-hash": "[[HASH_H1]]",
+// CHECK-NEXT:               "context-hash": "[[HASH_H1_DINCLUDE]]",
 // CHECK-NEXT:               "module-name": "header1"
 // CHECK-NEXT:             }
 // CHECK-NEXT:           ],
 // CHECK-NEXT:           "command-line": [
 // CHECK-NOT:              "-fimplicit-modules"
 // CHECK-NOT:              "-fimplicit-module-maps"
-// CHECK:                  "-fmodule-file={{.*}}[[PREFIX]]/module-cache{{(_clangcl)?}}/[[HASH_H1]]/header1-{{[A-Z0-9]+}}.pcm"
+// CHECK:                  "-fmodule-file={{.*}}[[PREFIX]]/module-cache{{(_clangcl)?}}/[[HASH_H1_DINCLUDE]]/header1-{{[A-Z0-9]+}}.pcm"
 // CHECK:                ],
 // CHECK-NEXT:           "executable": "{{.*}}clang{{.*}}"
 // CHECK-NEXT:           "file-deps": [
-// CHECK-NEXT:             "[[PREFIX]]/modules_cdb_input.cpp"
+// CHECK-NEXT:             "[[PREFIX]]/modules_cdb_input2.cpp"
 // CHECK-NEXT:           ],
-// CHECK-NEXT:           "input-file": "[[PREFIX]]/modules_cdb_input.cpp"
+// CHECK-NEXT:           "input-file": "[[PREFIX]]/modules_cdb_input2.cpp"
 // CHECK-NEXT:         }
 // CHECK-NEXT:       ]
 // CHECK-NEXT:     },
 // CHECK-NEXT:     {
 // CHECK-NEXT:       "commands": [
 // CHECK-NEXT:         {
 // CHECK-NEXT:           "clang-context-hash": "[[HASH_TU:[A-Z0-9]+]]",
 // CHECK-NEXT:           "clang-module-deps": [

 // CHECK-NEXT:           ],
 // CHECK-NEXT:           "input-file": "[[PREFIX]]/modules_cdb_input.cpp"
 // CHECK-NEXT:         }
 // CHECK-NEXT:       ]
 // CHECK-NEXT:     },
 // CHECK-NEXT:     {
 // CHECK-NEXT:       "commands": [
 // CHECK-NEXT:         {
-// CHECK-NEXT:           "clang-context-hash": "[[HASH_TU_DINCLUDE:[A-Z0-9]+]]",
+// CHECK-NEXT:           "clang-context-hash": "[[HASH_TU:[A-Z0-9]+]]",
 // CHECK-NEXT:           "clang-module-deps": [
 // CHECK-NEXT:             {
-// CHECK-NEXT:               "context-hash": "[[HASH_H1_DINCLUDE]]",
+// CHECK-NEXT:               "context-hash": "[[HASH_H1]]",
 // CHECK-NEXT:               "module-name": "header1"
 // CHECK-NEXT:             }
 // CHECK-NEXT:           ],
 // CHECK-NEXT:           "command-line": [
 // CHECK-NOT:              "-fimplicit-modules"
 // CHECK-NOT:              "-fimplicit-module-maps"
-// CHECK:                  "-fmodule-file={{.*}}[[PREFIX]]/module-cache{{(_clangcl)?}}/[[HASH_H1_DINCLUDE]]/header1-{{[A-Z0-9]+}}.pcm"
+// CHECK:                  "-fmodule-file={{.*}}[[PREFIX]]/module-cache{{(_clangcl)?}}/[[HASH_H1]]/header1-{{[A-Z0-9]+}}.pcm"
 // CHECK:                ],
 // CHECK-NEXT:           "executable": "{{.*}}clang{{.*}}"
 // CHECK-NEXT:           "file-deps": [
-// CHECK-NEXT:             "[[PREFIX]]/modules_cdb_input2.cpp"
+// CHECK-NEXT:             "[[PREFIX]]/modules_cdb_input.cpp"
 // CHECK-NEXT:           ],
-// CHECK-NEXT:           "input-file": "[[PREFIX]]/modules_cdb_input2.cpp"
+// CHECK-NEXT:           "input-file": "[[PREFIX]]/modules_cdb_input.cpp"
 // CHECK-NEXT:         }
 // CHECK-NEXT:       ]
 // CHECK-NEXT:     }
 // CHECK-NEXT:   ]
 // CHECK-NEXT: }

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

for (const ModuleID &MID : V)
     Ret.push_back(llvm::json::Object(
         {{"module-name", MID.ModuleName}, {"context-hash", MID.ContextHash}}));
   return Ret;
 }
 
 // Thread safe.
 class FullDeps {
 public:
+  FullDeps(size_t NumInputs) : Inputs(NumInputs) {}
+
   void mergeDeps(StringRef Input, TranslationUnitDeps TUDeps,
                  size_t InputIndex) {
     mergeDeps(std::move(TUDeps.ModuleGraph), InputIndex);
 
     InputDeps ID;
     ID.FileName = std::string(Input);
     ID.ContextHash = std::move(TUDeps.ID.ContextHash);
     ID.FileDeps = std::move(TUDeps.FileDeps);
     ID.ModuleDeps = std::move(TUDeps.ClangModuleDeps);
     ID.DriverCommandLine = std::move(TUDeps.DriverCommandLine);
     ID.Commands = std::move(TUDeps.Commands);
 
-    std::unique_lock<std::mutex> ul(Lock);
-    Inputs.push_back(std::move(ID));
+    assert(InputIndex < Inputs.size() && "Input index out of bounds");
+    assert(Inputs[InputIndex].FileName.empty() && "Result already populated");
+    Inputs[InputIndex] = std::move(ID);
   }
 
   void mergeDeps(ModuleDepsGraph Graph, size_t InputIndex) {
     std::unique_lock<std::mutex> ul(Lock);
     for (const ModuleDeps &MD : Graph) {
       auto I = Modules.find({MD.ID, 0});
       if (I != Modules.end()) {
         I->first.InputIndex = std::min(I->first.InputIndex, InputIndex);
void printFullOutput(raw_ostream &OS) {
     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(Inputs, [](const InputDeps &A, const InputDeps &B) {
-      return A.FileName < B.FileName;
-    });
-
     using namespace llvm::json;
 
     Array OutModules;
     for (auto &&ModID : ModuleIDs) {
       auto &MD = Modules[ModID];
       Object O{
           {"name", MD.ID.ModuleName},
           {"context-hash", MD.ID.ContextHash},
int main(int argc, const char **argv) {
   std::vector<std::unique_ptr<DependencyScanningTool>> WorkerTools;
   for (unsigned I = 0; I < Pool.getThreadCount(); ++I)
     WorkerTools.push_back(std::make_unique<DependencyScanningTool>(Service));
 
   std::vector<tooling::CompileCommand> Inputs =
       AdjustingCompilations->getAllCompileCommands();
 
   std::atomic<bool> HadErrors(false);
-  FullDeps FD;
+  std::optional<FullDeps> FD;
   P1689Deps PD;
   std::mutex Lock;
   size_t Index = 0;
 
+  if (Format == ScanningOutputFormat::Full)
+    FD.emplace(ModuleName.empty() ? Inputs.size() : 0);
+
   if (Verbose) {
     llvm::outs() << "Running clang-scan-deps on " << Inputs.size()
                  << " files using " << Pool.getThreadCount() << " workers\n";
   }
   for (unsigned I = 0; I < Pool.getThreadCount(); ++I) {
     Pool.async([I, &Lock, &Index, &Inputs, &HadErrors, &FD, &PD, &WorkerTools,
                 &DependencyOS, &Errs]() {
       llvm::StringSet<> AlreadySeenModules;
Pool.async([I, &Lock, &Index, &Inputs, &HadErrors, &FD, &PD, &WorkerTools,
             if (handleMakeDependencyToolResult(Filename, MaybeOutput,
                                                MakeformatOS, Errs))
               HadErrors = true;
           }
         } else if (MaybeModuleName) {
           auto MaybeModuleDepsGraph = WorkerTools[I]->getModuleDependencies(
               *MaybeModuleName, Input->CommandLine, CWD, AlreadySeenModules,
               LookupOutput);
-          if (handleModuleResult(*MaybeModuleName, MaybeModuleDepsGraph, FD,
+          if (handleModuleResult(*MaybeModuleName, MaybeModuleDepsGraph, *FD,
                                  LocalIndex, DependencyOS, Errs))
             HadErrors = true;
         } else {
           auto MaybeTUDeps = WorkerTools[I]->getTranslationUnitDependencies(
               Input->CommandLine, CWD, AlreadySeenModules, LookupOutput);
-          if (handleTranslationUnitResult(Filename, MaybeTUDeps, FD, LocalIndex,
-                                          DependencyOS, Errs))
+          if (handleTranslationUnitResult(Filename, MaybeTUDeps, *FD,
+                                          LocalIndex, DependencyOS, Errs))
             HadErrors = true;
         }
       }
     });
   }
   Pool.wait();
 
   if (RoundTripArgs)
-    if (FD.roundTripCommands(llvm::errs()))
+    if (FD && FD->roundTripCommands(llvm::errs()))
       HadErrors = true;
 
   if (Format == ScanningOutputFormat::Full)
-    FD.printFullOutput(llvm::outs());
+    FD->printFullOutput(llvm::outs());
   else if (Format == ScanningOutputFormat::P1689)
     PD.printDependencies(llvm::outs());
 
   return HadErrors;
 }