[clang][modules][deps] Preserve module map load order

[jansvoboda11]

Summary

In ASTWriter, input files are sorted based on whether they are system or user. The current implementation used single std::queue with push_back and push_front. This resulted in the user files being reversed.

This patch fixes that by keeping the system/user distinction, but otherwise serializing files in the order they were loaded by the SourceManager. This is then used in the dependency scanner to report module map dependencies in the correct order.

Depends on D134224.

[Bigcheese]

lgtm

clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp

129

This is loop invariant and can be pulled out.

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

struct ModuleDeps {
   /// The path to where an implicit build would put the PCM for this module.
   std::string ImplicitModulePCMPath;
 
   /// A collection of absolute paths to files that this module directly depends
   /// on, not including transitive dependencies.
   llvm::StringSet<> FileDeps;
 
   /// A collection of absolute paths to module map files that this module needs
-  /// to know about.
+  /// to know about. The ordering is significant.
   std::vector<std::string> ModuleMapFileDeps;
 
   /// A collection of prebuilt modular dependencies this module directly depends
   /// on, not including transitive dependencies.
   std::vector<PrebuiltModuleDep> PrebuiltModuleDeps;
 
   /// A list of module identifiers this module directly depends on, not
   /// including transitive dependencies.
private:
 
   /// Constructs a CompilerInvocation that can be used to build the given
   /// module, excluding paths to discovered modular dependencies that are yet to
   /// be built.
   CompilerInvocation makeInvocationForModuleBuildWithoutOutputs(
       const ModuleDeps &Deps,
       llvm::function_ref<void(CompilerInvocation &)> Optimize) const;
 
+  /// Collect module map files for given modules.
+  llvm::StringSet<>
+  collectModuleMapFiles(ArrayRef<ModuleID> ClangModuleDeps) const;
+
   /// Add module map files to the invocation, if needed.
   void addModuleMapFiles(CompilerInvocation &CI,
                          ArrayRef<ModuleID> ClangModuleDeps) const;
   /// Add module files (pcm) to the invocation, if needed.
   void addModuleFiles(CompilerInvocation &CI,
                       ArrayRef<ModuleID> ClangModuleDeps) const;
 
   /// Add paths that require looking up outputs to the given dependencies.

clang/lib/Serialization/ASTWriter.cpp

 #include "llvm/Support/VersionTuple.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <cstdlib>
 #include <cstring>
 #include <ctime>
-#include <deque>
 #include <limits>
 #include <memory>
 #include <queue>
 #include <tuple>
 #include <utility>
 #include <vector>
 
 using namespace clang;
void ASTWriter::WriteInputFiles(
 
   // Create input file hash abbreviation.
   auto IFHAbbrev = std::make_shared<BitCodeAbbrev>();
   IFHAbbrev->Add(BitCodeAbbrevOp(INPUT_FILE_HASH));
   IFHAbbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   IFHAbbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
   unsigned IFHAbbrevCode = Stream.EmitAbbrev(std::move(IFHAbbrev));
 
-  // Get all ContentCache objects for files, sorted by whether the file is a
-  // system one or not. System files go at the back, users files at the front.
-  std::deque<InputFileEntry> SortedFiles;
+  // Get all ContentCache objects for files.
+  std::vector<InputFileEntry> UserFiles;
+  std::vector<InputFileEntry> SystemFiles;
   for (unsigned I = 1, N = SourceMgr.local_sloc_entry_size(); I != N; ++I) {
     // Get this source location entry.
     const SrcMgr::SLocEntry *SLoc = &SourceMgr.getLocalSLocEntry(I);
     assert(&SourceMgr.getSLocEntry(FileID::get(I)) == SLoc);
 
     // We only care about file entries that were not overridden.
     if (!SLoc->isFile())
       continue;
for (unsigned I = 1, N = SourceMgr.local_sloc_entry_size(); I != N; ++I) {
     }
     auto CH = llvm::APInt(64, ContentHash);
     Entry.ContentHash[0] =
         static_cast<uint32_t>(CH.getLoBits(32).getZExtValue());
     Entry.ContentHash[1] =
         static_cast<uint32_t>(CH.getHiBits(32).getZExtValue());
 
     if (Entry.IsSystemFile)
-      SortedFiles.push_back(Entry);
+      SystemFiles.push_back(Entry);
     else
-      SortedFiles.push_front(Entry);
+      UserFiles.push_back(Entry);
   }
 
+  // User files go at the front, system files at the back.
+  auto SortedFiles = llvm::concat<InputFileEntry>(std::move(UserFiles),
+                                                  std::move(SystemFiles));
+
   unsigned UserFilesNum = 0;
   // Write out all of the input files.
   std::vector<uint64_t> InputFileOffsets;
   for (const auto &Entry : SortedFiles) {
     uint32_t &InputFileID = InputFileIDs[Entry.File];
     if (InputFileID != 0)
       continue; // already recorded this file.
 

clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp

ModuleDepCollector::makeInvocationForModuleBuildWithoutOutputs(
   CI.getLangOpts()->ModuleName = Deps.ID.ModuleName;
   CI.getFrontendOpts().IsSystemModule = Deps.IsSystem;
 
   // Inputs
   InputKind ModuleMapInputKind(CI.getFrontendOpts().DashX.getLanguage(),
                                InputKind::Format::ModuleMap);
   CI.getFrontendOpts().Inputs.emplace_back(Deps.ClangModuleMapFile,
                                            ModuleMapInputKind);
-  CI.getFrontendOpts().ModuleMapFiles = Deps.ModuleMapFileDeps;
-  addModuleMapFiles(CI, Deps.ClangModuleDeps);
+
+  auto CurrentModuleMapEntry =
+      ScanInstance.getFileManager().getFile(Deps.ClangModuleMapFile);
+  assert(CurrentModuleMapEntry && "module map file entry not found");
+
+  auto DepModuleMapFiles = collectModuleMapFiles(Deps.ClangModuleDeps);
+  for (StringRef ModuleMapFile : Deps.ModuleMapFileDeps) {
+    // Don't report module maps describing eagerly-loaded dependency. This
+    // information will be deserialized from the PCM.
+    // TODO: Verify this works fine when modulemap for module A is eagerly
+    // loaded from A.pcm, and module map passed on the command line contains
+    // definition of a submodule: "explicit module A.Private { ... }".
+    if (EagerLoadModules && DepModuleMapFiles.contains(ModuleMapFile))
+      continue;
+
+    // TODO: Track these as `FileEntryRef` to simplify the equality check below.
+    auto ModuleMapEntry = ScanInstance.getFileManager().getFile(ModuleMapFile);
+    assert(ModuleMapEntry && "module map file entry not found");
+
+    // Don't report module map file of the current module unless it also
+    // describes a dependency (for symmetry).
+    if (*ModuleMapEntry == *CurrentModuleMapEntry &&
+        !DepModuleMapFiles.contains(ModuleMapFile))
+      continue;
+
+    CI.getFrontendOpts().ModuleMapFiles.emplace_back(ModuleMapFile);
+  }
 
   // Report the prebuilt modules this module uses.
   for (const auto &PrebuiltModule : Deps.PrebuiltModuleDeps)
     CI.getFrontendOpts().ModuleFiles.push_back(PrebuiltModule.PCMFile);
 
   // Remove any macro definitions that are explicitly ignored.
   if (!CI.getHeaderSearchOpts().ModulesIgnoreMacros.empty()) {
     llvm::erase_if(
ModuleDepCollector::makeInvocationForModuleBuildWithoutOutputs(
   // reporting dependencies to the clients. Let's make sure we're using
   // **strict** context hash in order to prevent accidental sharing of
   // incompatible modules (e.g. with differences in search paths).
   CI.getHeaderSearchOpts().ModulesStrictContextHash = true;
 
   return CI;
 }
 
+llvm::StringSet<> ModuleDepCollector::collectModuleMapFiles(
+    ArrayRef<ModuleID> ClangModuleDeps) const {
+  llvm::StringSet<> ModuleMapFiles;
+  for (const ModuleID &MID : ClangModuleDeps) {
+    ModuleDeps *MD = ModuleDepsByID.lookup(MID);
+    assert(MD && "Inconsistent dependency info");
+    ModuleMapFiles.insert(MD->ClangModuleMapFile);
+  }
+  return ModuleMapFiles;
+}
+
 void ModuleDepCollector::addModuleMapFiles(
     CompilerInvocation &CI, ArrayRef<ModuleID> ClangModuleDeps) const {
   if (EagerLoadModules)
     return; // Only pcm is needed for eager load.
 
   for (const ModuleID &MID : ClangModuleDeps) {
     ModuleDeps *MD = ModuleDepsByID.lookup(MID);
     assert(MD && "Inconsistent dependency info");
if (Module *CurrentModule = PP.getCurrentModuleImplementation())
         CI.getFrontendOpts().ModuleMapFiles.emplace_back(
             CurrentModuleMap->getName());
 
     SmallVector<ModuleID> DirectDeps;
     for (const auto &KV : ModularDeps)
       if (KV.second->ImportedByMainFile)
         DirectDeps.push_back(KV.second->ID);
 
+    // TODO: Report module maps the same way it's done for modular dependencies.
     addModuleMapFiles(CI, DirectDeps);
+
     addModuleFiles(CI, DirectDeps);
 
     for (const auto &KV : DirectPrebuiltModularDeps)
       CI.getFrontendOpts().ModuleFiles.push_back(KV.second.PCMFile);
   }
 }
 
 static std::string getModuleContextHash(const ModuleDeps &MD,
MDC.ScanInstance.getASTReader()->visitInputFiles(
         MDC.addFileDep(MD, IF.getFile()->getName());
       });
 
   llvm::DenseSet<const Module *> SeenDeps;
   addAllSubmodulePrebuiltDeps(M, MD, SeenDeps);
   addAllSubmoduleDeps(M, MD, SeenDeps);
   addAllAffectingModules(M, MD, SeenDeps);
 
-  llvm::DenseSet<const FileEntry *> SeenModuleMaps;
-  for (const Module *SM : SeenDeps)
-    if (const FileEntry *SMM = MDC.ScanInstance.getPreprocessor()
-                                   .getHeaderSearchInfo()
-                                   .getModuleMap()
-                                   .getModuleMapFileForUniquing(SM))
-      SeenModuleMaps.insert(SMM);
-
   MDC.ScanInstance.getASTReader()->visitTopLevelModuleMaps(
       *MF, [&](const FileEntry *FE) {
         if (FE->getName().endswith("__inferred_module.map"))
           return;
-        // The top-level modulemap of this module will be the input file. We
-        // don't need to specify it via "-fmodule-map-file=".
-        if (FE == ModuleMap)
-          return;
-        // The top-level modulemap of dependencies will be serialized in the PCM
-        // file (eager loading mode) or passed on the command-line through a
-        // different mechanism (lazy loading mode).
-        if (SeenModuleMaps.contains(FE))
-          return;
         MD.ModuleMapFileDeps.emplace_back(FE->getName());
       });
 
   CompilerInvocation CI = MDC.makeInvocationForModuleBuildWithoutOutputs(
       MD, [&](CompilerInvocation &BuildInvocation) {
         if (MDC.OptimizeArgs)
           optimizeHeaderSearchOpts(BuildInvocation.getHeaderSearchOpts(),
                                    *MDC.ScanInstance.getASTReader(), *MF);

clang/test/ClangScanDeps/modules-module-map-order.m

+// RUN: rm -rf %t
+// RUN: split-file %s %t
+
+//--- this/module.modulemap
+module This { header "This.h" }
+//--- this/This.h
+#include "Foo.h"
+#include "Foo_Private_Excluded.h"
+
+//--- modules/module.modulemap
+module Foo { header "Foo.h" }
+//--- modules/module.private.modulemap
+explicit module Foo.Private {
+  header "Foo_Private.h"
+  exclude header "Foo_Private_Excluded.h"
+}
+//--- modules/Foo.h
+//--- modules/Foo_Private.h
+//--- modules/Foo_Private_Excluded.h
+
+//--- cdb.json.template
+[{
+  "file": "DIR/tu.m",
+  "directory": "DIR",
+  "command": "clang -fmodules -fmodules-cache-path=DIR/cache -I DIR/this -I DIR/modules -c DIR/tu.m -o DIR/tu.o"
+}]
+
+//--- tu.m
+@import This;
+
+// RUN: sed -e "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 %s -DPREFIX=%/t
+// CHECK:      {
+// CHECK-NEXT:   "modules": [
+// CHECK-NEXT:     {
+// CHECK:          },
+// CHECK-NEXT:     {
+// CHECK:            "command-line": [
+// CHECK:              "-fmodule-map-file=[[PREFIX]]/modules/module.modulemap",
+// CHECK-NEXT:         "-fmodule-map-file=[[PREFIX]]/modules/module.private.modulemap",
+// CHECK:            ],
+// CHECK:            "name": "This"
+// CHECK-NEXT:     }
+// CHECK-NEXT:   ]
+// CHECK:      }
+
+// RUN: %deps-to-rsp %t/result.json --module-name=Foo > %t/Foo.cc1.rsp
+// RUN: %deps-to-rsp %t/result.json --module-name=This > %t/This.cc1.rsp
+// RUN: %deps-to-rsp %t/result.json --tu-index=0 > %t/tu.rsp
+
+// RUN: %clang @%t/Foo.cc1.rsp
+// RUN: %clang @%t/This.cc1.rsp
+// RUN: %clang @%t/tu.rsp

clang/test/Index/Core/index-with-module.m

 }
 
 // CHECK: ==== Module ModA ====
 // CHECK-DAG: 3:9 | macro/C | MODA_MACRO | c:{{.*}}@macro@MODA_MACRO | Def |
 // CHECK-DAG: 3:9 | macro/C | SUBMODA_MACRO | c:{{.*}}@macro@SUBMODA_MACRO | Def |
 // CHECK-DAG: 2:6 | function/C | ModA_func | c:@F@ModA_func | {{.*}} | Decl | rel: 0
 // CHECK-DAG: 2:6 | function/C | SubModA_func | c:@F@SubModA_func | {{.*}} | Decl | rel: 0
 // CHECK: ---- Module Inputs ----
-// CHECK: user | {{.*}}ModA.h
 // CHECK: user | {{.*}}module.modulemap
+// CHECK: user | {{.*}}ModA.h

clang/test/Modules/module-file-home-is-cwd.m

 // RUN: cd %S
 // RUN: %clang_cc1 -fmodules -fno-implicit-modules -fmodule-file-home-is-cwd -fmodule-name=libA -emit-module Inputs/normal-module-map/module.map -o %t/mod.pcm
 // RUN: llvm-bcanalyzer --dump --disable-histogram %t/mod.pcm | FileCheck %s
 
-// CHECK: <INPUT_FILE {{.*}}/> blob data = 'Inputs{{/|\\}}normal-module-map{{/|\\}}a1.h'
-// CHECK: <INPUT_FILE {{.*}}/> blob data = 'Inputs{{/|\\}}normal-module-map{{/|\\}}a2.h'
 // CHECK: <INPUT_FILE {{.*}}/> blob data = 'Inputs{{/|\\}}normal-module-map{{/|\\}}module.map'
+// CHECK: <INPUT_FILE {{.*}}/> blob data = 'Inputs{{/|\\}}normal-module-map{{/|\\}}a2.h'
+// CHECK: <INPUT_FILE {{.*}}/> blob data = 'Inputs{{/|\\}}normal-module-map{{/|\\}}a1.h'
 // CHECK-NOT: MODULE_DIRECTORY

clang/test/Modules/module_file_info.m

 // CHECK:   Use libc++ (rather than libstdc++) [-stdlib=]:
 
 // CHECK: Preprocessor options:
 // CHECK:   Uses compiler/target-specific predefines [-undef]: Yes
 // CHECK:   Uses detailed preprocessing record (for indexing): No
 // CHECK:   Predefined macros:
 // CHECK:     -DBLARG
 // CHECK:     -DWIBBLE=WOBBLE
-// CHECK: Input file: {{.*}}DependsOnModulePrivate.h
-// CHECK-NEXT: Input file: {{.*}}Other.h
-// CHECK-NEXT: Input file: {{.*}}SubFramework.h
-// CHECK-NEXT: Input file: {{.*}}not_coroutines.h
-// CHECK-NEXT: Input file: {{.*}}not_cxx.h
-// CHECK-NEXT: Input file: {{.*}}other.h
-// CHECK-NEXT: Input file: {{.*}}module.map
-// CHECK-NEXT: Input file: {{.*}}DependsOnModule.h
+// CHECK: Input file: {{.*}}module.map
 // CHECK-NEXT: Input file: {{.*}}module_private.map
+// CHECK-NEXT: Input file: {{.*}}DependsOnModule.h
 // CHECK-NEXT: Input file: {{.*}}module.map
+// CHECK-NEXT: Input file: {{.*}}other.h
+// CHECK-NEXT: Input file: {{.*}}not_cxx.h
+// CHECK-NEXT: Input file: {{.*}}not_coroutines.h
+// CHECK-NEXT: Input file: {{.*}}SubFramework.h
+// CHECK-NEXT: Input file: {{.*}}Other.h
+// CHECK-NEXT: Input file: {{.*}}DependsOnModulePrivate.h
 
 // CHECK: Diagnostic options:
 // CHECK:   IgnoreWarnings: Yes
 // CHECK:   Diagnostic flags:
 // CHECK:     -Wunused