[clang][deps] Sort submodules when calculating dependencies

[benlangmuir]

Summary

Dependency scanning does not care about the order of submodules for correctness, so sort the submodules so that we get the same command-lines to build the module across different TUs. Otherwise, the order of inferred submodules can vary depending on the order of #includes in the including TU.

Note: a true canonical order for Module::submodules would probably be to match the order of module decls within the modulemap file and sort the header files for any inferred modules, but that might be expensive to compute all the time (requires iterating a directory in the filesystem).

[jansvoboda11]

Interesting edge-case. LGTM.

clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp

ModuleID ModuleDepCollectorPP::handleTopLevelModule(const Module *M) {
   MD.ID.ContextHash = MD.BuildInvocation.getModuleHash();
 
   llvm::DenseSet<const Module *> AddedModules;
   addAllSubmoduleDeps(M, MD, AddedModules);
 
   return MD.ID;
 }
 
+static void forEachSubmoduleSorted(const Module *M,
+                                   llvm::function_ref<void(const Module *)> F) {
+  // Submodule order depends on order of header includes for inferred submodules
+  // we don't care about the exact order, so sort so that it's consistent across
+  // TUs to improve sharing.
+  SmallVector<const Module *> Submodules(M->submodule_begin(),
+                                         M->submodule_end());
+  llvm::stable_sort(Submodules, [](const Module *A, const Module *B) {
+    return A->Name < B->Name;
+  });
+  for (const Module *SubM : Submodules)
+    F(SubM);
+}
+
 void ModuleDepCollectorPP::addAllSubmodulePrebuiltDeps(
     const Module *M, ModuleDeps &MD,
     llvm::DenseSet<const Module *> &SeenSubmodules) {
   addModulePrebuiltDeps(M, MD, SeenSubmodules);
 
-  for (const Module *SubM : M->submodules())
+  forEachSubmoduleSorted(M, [&](const Module *SubM) {
     addAllSubmodulePrebuiltDeps(SubM, MD, SeenSubmodules);
+  });
 }
 
 void ModuleDepCollectorPP::addModulePrebuiltDeps(
     const Module *M, ModuleDeps &MD,
     llvm::DenseSet<const Module *> &SeenSubmodules) {
   for (const Module *Import : M->Imports)
     if (Import->getTopLevelModule() != M->getTopLevelModule())
       if (MDC.isPrebuiltModule(Import->getTopLevelModule()))
         if (SeenSubmodules.insert(Import->getTopLevelModule()).second)
           MD.PrebuiltModuleDeps.emplace_back(Import->getTopLevelModule());
 }
 
 void ModuleDepCollectorPP::addAllSubmoduleDeps(
     const Module *M, ModuleDeps &MD,
     llvm::DenseSet<const Module *> &AddedModules) {
   addModuleDep(M, MD, AddedModules);
 
-  for (const Module *SubM : M->submodules())
+  forEachSubmoduleSorted(M, [&](const Module *SubM) {
     addAllSubmoduleDeps(SubM, MD, AddedModules);
+  });
 }
 
 void ModuleDepCollectorPP::addModuleDep(
     const Module *M, ModuleDeps &MD,
     llvm::DenseSet<const Module *> &AddedModules) {
   for (const Module *Import : M->Imports) {
     if (Import->getTopLevelModule() != M->getTopLevelModule() &&
         !MDC.isPrebuiltModule(Import)) {

clang/test/ClangScanDeps/submodule-order.c

+// RUN: rm -rf %t
+// RUN: split-file %s %t
+// 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 -generate-modules-path-args > %t/deps1.json
+// RUN: mv %t/tu2.c %t/tu.c
+// RUN: clang-scan-deps -compilation-database %t/cdb.json -format experimental-full -generate-modules-path-args > %t/deps2.json
+// RUN: diff -u %t/deps1.json %t/deps2.json
+// RUN: FileCheck %s < %t/deps1.json
+
+// CHECK: "-fmodule-file={{.*}}Indirect1
+// CHECK-NOT: "-fmodule-file={{.*}}Indirect
+// CHECK: "-fmodule-file={{.*}}Indirect2
+// CHECK-NOT: "-fmodule-file={{.*}}Indirect
+
+//--- cdb.json.template
+[{
+  "directory": "DIR",
+  "command": "clang -fsyntax-only DIR/tu.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+  "file": "DIR/tu.c"
+}]
+
+//--- module.modulemap
+module Indirect1 { header "Indirect1.h" }
+module Indirect2 { header "Indirect2.h" }
+module Mod {
+  umbrella "Mod"
+  module * { export * }
+}
+
+//--- Indirect1.h
+void indirect1(void);
+
+//--- Indirect2.h
+void indirect2(void);
+
+//--- Mod/SubMod1.h
+#include "../Indirect1.h"
+
+//--- Mod/SubMod2.h
+#include "../Indirect2.h"
+
+//--- tu.c
+#include "Mod/SubMod1.h"
+#include "Mod/SubMod2.h"
+void tu1(void) {
+  indirect1();
+  indirect2();
+}
+
+//--- tu2.c
+#include "Mod/SubMod2.h"
+#include "Mod/SubMod1.h"
+void tu1(void) {
+  indirect1();
+  indirect2();
+}
 No newline at end of file