[clang][modules][deps] WIP: In-memory module transfer

[jansvoboda11]

Summary

Let's not create PCM files in the dependency scanner.

[jansvoboda11]

Improve SourceLocation handling: invalid & inside predefines buffer.

[jansvoboda11]

Handle macros

[jansvoboda11]

Kinda rebase

[jansvoboda11]

Fixed two tests:

• modules-pch.c by always marking identifier info as not out-of-date when getting leaf module macros,
• modules-module-map-order.m by updating the sorting logic for gathering SortedFiles.

[jansvoboda11]

Using CompilerInstance as the module storage dramatically increases memory usage (peak ~30GB) of clang-scan-deps when scanning LLVM. (Memory mapping serialized files peaks at ~300MB.)

clang/include/clang/Frontend/CompilerInstance.h

class CompilerInstance : public ModuleLoader {
   std::list<OutputFile> OutputFiles;
 
   /// Force an output buffer.
   std::unique_ptr<llvm::raw_pwrite_stream> OutputStream;
 
   CompilerInstance(const CompilerInstance &) = delete;
   void operator=(const CompilerInstance &) = delete;
 public:
+  struct EntryStruct {
+    Optional<FileEntryRef> FE;
+    bool IsSystemFile;
+    bool IsTopLevelModuleMap;
+  };
+  llvm::StringMap<std::deque<EntryStruct>> SortedFiles;
+  llvm::StringMap<llvm::BitVector> SearchPathUsage;
+
   explicit CompilerInstance(
       std::shared_ptr<PCHContainerOperations> PCHContainerOps =
           std::make_shared<PCHContainerOperations>(),
       InMemoryModuleCache *SharedModuleCache = nullptr);
   ~CompilerInstance() override;
 
   /// @name High-Level Operations
   /// {

clang/include/clang/Lex/PreprocessorOptions.h

 /// PreprocessorOptions - This class is used for passing the various options
 /// used in preprocessor initialization to InitializePreprocessor().
 class PreprocessorOptions {
 public:
   std::vector<std::pair<std::string, bool/*isUndef*/>> Macros;
   std::vector<std::string> Includes;
   std::vector<std::string> MacroIncludes;
 
+  bool ScanningMode = false;
+
   /// Initialize the preprocessor with the compiler and target specific
   /// predefines.
   bool UsePredefines = true;
 
   /// Whether we should maintain a detailed record of all macro
   /// definitions and expansions.
   bool DetailedRecord = false;
 

clang/include/clang/Lex/Token.h

bool getFlag(TokenFlags Flag) const {
     return (Flags & Flag) != 0;
   }
 
   /// Unset the specified flag.
   void clearFlag(TokenFlags Flag) {
     Flags &= ~Flag;
   }
 
-  /// Return the internal represtation of the flags.
+  /// Return the internal representation of the flags.
   ///
   /// This is only intended for low-level operations such as writing tokens to
   /// disk.
   unsigned getFlags() const {
     return Flags;
   }
 
+  /// Set the internal representation of the flags.
+  ///
+  /// This is only intended for low-level operations such as writing tokens to
+  /// disk.
+  void setFlags(unsigned Flags) {
+    this->Flags = Flags;
+  }
+
   /// Set a flag to either true or false.
   void setFlagValue(TokenFlags Flag, bool Val) {
     if (Val)
       setFlag(Flag);
     else
       clearFlag(Flag);
   }
 

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

struct ModuleDeps {
   bool IsSystem;
 
   /// The path to the modulemap file which defines this module.
   ///
   /// This can be used to explicitly build this module. This file will
   /// additionally appear in \c FileDeps as a dependency.
   std::string ClangModuleMapFile;
 
-  /// 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. The ordering is significant.
   std::vector<std::string> ModuleMapFileDeps;
 

clang/lib/Frontend/CompilerInstance.cpp

if (LangOpts.OpenCL)
     return Language::OpenCL;
   if (LangOpts.CUDA)
     return Language::CUDA;
   if (LangOpts.ObjC)
     return LangOpts.CPlusPlus ? Language::ObjCXX : Language::ObjC;
   return LangOpts.CPlusPlus ? Language::CXX : Language::C;
 }
 
+class Translator {
+  CompilerInstance &A;
+  Preprocessor &APP;
+  SourceManager &ASM;
+  FileManager &AFM;
+  HeaderSearch &AHS;
+
+  const CompilerInstance &B;
+  const Preprocessor &BPP;
+  const SourceManager &BSM;
+  const FileManager &BFM;
+  HeaderSearch &BHS;
+
+  llvm::StringSet<> TranslatedModules;
+
+public:
+  Translator(CompilerInstance &A, const CompilerInstance &B)
+      : A(A), APP(A.getPreprocessor()), ASM(A.getSourceManager()),
+        AFM(A.getFileManager()), AHS(A.getPreprocessor().getHeaderSearchInfo()),
+        B(B), BPP(B.getPreprocessor()), BSM(B.getSourceManager()),
+        BFM(B.getFileManager()),
+        BHS(B.getPreprocessor().getHeaderSearchInfo()) {}
+
+  template <class T> Optional<T> translate(const Optional<T> &BO) {
+    if (!BO)
+      return None;
+    return translate(*BO);
+  }
+
+  template <class T> const T *translate(const T *BP) {
+    if (!BP)
+      return nullptr;
+    return &translate(*BP);
+  }
+
+  template <class T> T *translate(T *BP) {
+    if (!BP)
+      return nullptr;
+    return &translate(*BP);
+  }
+
+  template <class T, class U>
+  llvm::PointerUnion<T, U> translate(llvm::PointerUnion<T, U> BPU) {
+    if (!BPU)
+      return nullptr;
+    if (BPU.template is<T>())
+      return translate(BPU.template get<T>());
+    return translate(BPU.template get<U>());
+  }
+
+  template <class T, unsigned N>
+  SmallVector<T, N> translate(const SmallVector<T, N> &BV) {
+    SmallVector<T, N> AV;
+    AV.reserve(BV.size());
+    for (const T &Entry : BV)
+      AV.push_back(translate(Entry));
+    return AV;
+  }
+
+  template <class T, unsigned N>
+  llvm::SmallSetVector<T, N> translate(const llvm::SmallSetVector<T, N>& BSSV) {
+    llvm::SmallSetVector<T, N> ASSV;
+    for (const auto &Entry : BSSV)
+      ASSV.insert(translate(Entry));
+    return ASSV;
+  }
+
+  const FileEntry &translate(const FileEntry &BFE) {
+    if (auto MaybeAFE = AFM.getFile(BFE.getName()))
+      return **MaybeAFE;
+    return *AFM.getVirtualFile(BFE.getName(), BFE.getSize(),
+                               BFE.getModificationTime());
+  }
+
+  FileEntryRef translate(FileEntryRef BFE) {
+    return *AFM.getOptionalFileRef(BFE.getName());
+  }
+
+  const DirectoryEntry &translate(const DirectoryEntry &BDE) {
+    return **AFM.getDirectory(BDE.getName());
+  }
+
+  SourceLocation translate(SourceLocation BLoc) {
+    if (BLoc.isInvalid())
+      return {};
+
+    auto BOffset = BSM.getFileOffset(BLoc);
+    auto AOffset = BOffset;
+
+    auto BFileID = BSM.getFileID(BLoc);
+    auto AFileID = [&]() {
+      if (BFileID == BPP.getPredefinesFileID())
+        return APP.getPredefinesFileID();
+
+      auto BFileCharacteristic = BSM.getFileCharacteristic(BLoc);
+      auto AFileCharacteristic = BFileCharacteristic;
+
+      auto *BFileEntry = BSM.getFileEntryForID(BFileID);
+      auto *AFileEntry = translate(BFileEntry);
+      return ASM.getOrCreateFileID(AFileEntry, AFileCharacteristic);
+    }();
+
+    return ASM.getComposedLoc(AFileID, AOffset);
+  }
+
+  Module::Header translate(const Module::Header &BHeader) {
+    return Module::Header{BHeader.NameAsWritten,
+                          BHeader.PathRelativeToRootModuleDirectory,
+                          translate(BHeader.Entry)};
+  }
+
+  std::vector<Module *> translate(Module::submodule_iterator Begin,
+                                  Module::submodule_iterator End) {
+    std::vector<Module *> ASubModules;
+    for (auto It = Begin; It != End; ++It)
+      ASubModules.push_back(translate(*It));
+    return ASubModules;
+  }
+
+  Module::UnresolvedHeaderDirective
+  translate(const Module::UnresolvedHeaderDirective &BD) {
+    return {BD.Kind, //
+            translate(BD.FileNameLoc),
+            BD.FileName,
+            BD.IsUmbrella,
+            BD.HasBuiltinHeader,
+            BD.Size,
+            BD.ModTime};
+  }
+
+  Module::ExportDecl translate(const Module::ExportDecl &BED) {
+    return {translate(BED.getPointer()), BED.getInt()};
+  }
+
+  ModuleId translate(const ModuleId &BId) {
+    ModuleId Res;
+    for (const auto &Element : BId)
+      Res.push_back({Element.first, translate(Element.second)});
+    return Res;
+  }
+
+  Module::UnresolvedExportDecl
+  translate(const Module::UnresolvedExportDecl &BUED) {
+    return {translate(BUED.ExportLoc), translate(BUED.Id), BUED.Wildcard};
+  }
+
+  Module::LinkLibrary translate(const Module::LinkLibrary &X) {
+    return X;
+  }
+
+  Module::UnresolvedConflict translate(const Module::UnresolvedConflict &X) {
+    return {translate(X.Id), X.Message};
+  }
+
+  Module::Conflict translate(const Module::Conflict &X) {
+    return {translate(X.Other), X.Message};
+  }
+
+  const Module &translate(const Module &BMod) {
+    return translate(const_cast<Module &>(BMod));
+  }
+
+  Module &translate(Module &BMod) {
+    auto &AModMap = AHS.getModuleMap();
+
+    auto [AMod, New] = AModMap.findOrCreateModule(
+        BMod.Name, translate(BMod.Parent),
+        BMod.IsFramework, BMod.IsExplicit);
+
+    if (!TranslatedModules.insert(BMod.Name).second)
+      return *AMod;
+
+    AMod->Kind = BMod.Kind;
+    AMod->Directory = translate(BMod.Directory);
+    AMod->PresumedModuleMapFile = BMod.PresumedModuleMapFile;
+    AMod->DefinitionLoc = translate(BMod.DefinitionLoc);
+    AMod->Umbrella = translate(BMod.Umbrella);
+    AMod->UmbrellaAsWritten = BMod.UmbrellaAsWritten;
+    AMod->UmbrellaRelativeToRootModuleDirectory =
+        BMod.UmbrellaRelativeToRootModuleDirectory;
+    AMod->ExportAsModule = BMod.ExportAsModule;
+
+    for (Module *BSubMod : BMod.submodules())
+      translate(BSubMod);
+
+    for (const FileEntry *BTopHeader : BMod.getTopHeaders(B.getFileManager()))
+      AMod->addTopHeader(translate(BTopHeader));
+
+    // TODO: Propagate VisibilityID to other data structures.
+
+    for (auto Kind : {Module::HK_Normal, Module::HK_Textual, Module::HK_Private,
+                      Module::HK_PrivateTextual, Module::HK_Excluded}) {
+      for (const auto &BH : BMod.Headers[Kind]) {
+        const auto &AH = translate(BH);
+        AModMap.addHeader(AMod, AH, ModuleMap::headerKindToRole(Kind),
+                          BHS.getFileInfo(BH.Entry).isModuleHeader);
+      }
+    }
+
+    AMod->UnresolvedHeaders = translate(BMod.UnresolvedHeaders);
+    AMod->MissingHeaders = translate(BMod.MissingHeaders);
+    AMod->Requirements = BMod.Requirements;
+    AMod->ShadowingModule = translate(BMod.ShadowingModule);
+    AMod->IsUnimportable = BMod.IsUnimportable;
+    AMod->HasIncompatibleModuleFile = BMod.HasIncompatibleModuleFile;
+    AMod->IsAvailable = BMod.IsAvailable;
+    AMod->IsFromModuleFile = BMod.IsFromModuleFile;
+    AMod->IsFramework = BMod.IsFramework;
+    AMod->IsExplicit = BMod.IsExplicit;
+    AMod->IsSystem = BMod.IsSystem;
+    AMod->IsExternC = BMod.IsExternC;
+    // This is being dropped by PCM files and propagating it triggers asserts.
+    // AMod->IsInferred = BMod.IsInferred;
+    AMod->InferSubmodules = BMod.InferSubmodules;
+    AMod->InferExplicitSubmodules = BMod.InferExplicitSubmodules;
+    AMod->InferExportWildcard = BMod.InferExportWildcard;
+    AMod->ConfigMacrosExhaustive = BMod.ConfigMacrosExhaustive;
+    AMod->NoUndeclaredIncludes = BMod.NoUndeclaredIncludes;
+    AMod->ModuleMapIsPrivate = BMod.ModuleMapIsPrivate;
+    AMod->NameVisibility = BMod.NameVisibility;
+    AMod->InferredSubmoduleLoc = translate(BMod.InferredSubmoduleLoc);
+    AMod->Imports = translate(BMod.Imports);
+    AMod->Exports = translate(BMod.Exports);
+    AMod->AffectingClangModules = translate(BMod.AffectingClangModules);
+    AMod->UnresolvedExports = translate(BMod.UnresolvedExports);
+    AMod->DirectUses = translate(BMod.DirectUses);
+    AMod->UnresolvedDirectUses = translate(BMod.UnresolvedDirectUses);
+    AMod->UndeclaredUses = translate(BMod.UndeclaredUses);
+    AMod->LinkLibraries = translate(BMod.LinkLibraries);
+    AMod->UseExportAsModuleLinkName = BMod.UseExportAsModuleLinkName;
+    AMod->ConfigMacros = BMod.ConfigMacros;
+    AMod->UnresolvedConflicts = BMod.UnresolvedConflicts;
+    AMod->Conflicts = BMod.Conflicts;
+
+    return *AMod;
+  }
+
+  void translateModule(StringRef BName) {
+    translate(B.getPreprocessor().getHeaderSearchInfo().lookupModule(BName));
+  }
+
+  IdentifierInfo &translate(IdentifierInfo &BII) {
+    auto &AII = APP.getIdentifierTable().getOwn(BII.getName());
+
+    AII.setOutOfDate(false);
+
+    // TODO: Check if is interesting.
+
+    if (BII.hasRevertedTokenIDToIdentifier() &&
+        BII.getTokenID() != tok::TokenKind::identifier)
+      AII.revertTokenIDToIdentifier();
+    AII.setObjCOrBuiltinID(BII.getObjCOrBuiltinID());
+    AII.setIsPoisoned(BII.isPoisoned());
+
+    AII.setObjCKeywordID(BII.getObjCKeywordID());
+    AII.setHasMacroDefinition(BII.hasMacroDefinition());
+
+    return AII;
+  }
+
+  Token translate(const Token &BTok) {
+    Token ATok;
+    ATok.startToken();
+    ATok.setLocation(translate(BTok.getLocation()));
+    ATok.setLength(BTok.getLength());
+    ATok.setIdentifierInfo(translate(BTok.getIdentifierInfo()));
+    ATok.setKind(BTok.getKind());
+    ATok.setFlags(BTok.getFlags());
+    return ATok;
+  }
+
+  MacroInfo *translate(MacroInfo *BMI) {
+    auto BLoc = BMI->getDefinitionLoc();
+    auto ALoc = translate(BLoc);
+
+    MacroInfo *AMI = APP.AllocateMacroInfo(ALoc);
+    AMI->setDefinitionEndLoc(BMI->getDefinitionEndLoc());
+    AMI->setIsUsed(BMI->isUsed());
+    AMI->setUsedForHeaderGuard(BMI->isUsedForHeaderGuard());
+
+    if (BMI->isFunctionLike()) {
+      AMI->setIsFunctionLike();
+      if (BMI->isC99Varargs())
+        AMI->setIsC99Varargs();
+      if (BMI->isGNUVarargs())
+        AMI->setIsGNUVarargs();
+      if (BMI->hasCommaPasting())
+        AMI->setHasCommaPasting();
+      std::vector<IdentifierInfo *> AParams;
+      for (const IdentifierInfo *BParam : BMI->params())
+        AParams.push_back(translate(const_cast<IdentifierInfo *>(BParam)));
+      AMI->setParameterList(AParams, APP.getPreprocessorAllocator());
+    }
+
+    // TODO: Complete preprocessing record.
+
+    std::vector<Token> AToks;
+    for (const Token &BTok : BMI->tokens())
+      AToks.push_back(translate(BTok));
+    AMI->setTokens(AToks, APP.getPreprocessorAllocator());
+
+    return AMI;
+  }
+
+  void translatePreprocessor() {
+    for (const auto &Entry : BPP.getIdentifierTable()) {
+      IdentifierInfo *BII = Entry.getValue();
+
+      if (!BII->hadMacroDefinition())
+        continue;
+
+      // Macro directive history is not read for modules.
+
+      IdentifierInfo *BName = BII;
+      IdentifierInfo *AName = translate(BII);
+
+      if (BII->isOutOfDate()) {
+        // TODO: Investigate how out-of-date identifiers come to be.
+        BII->setOutOfDate(false);
+      }
+
+      auto BLeafs = BPP.getLeafModuleMacros(BName);
+      SmallVector<ModuleMacro *, 8> Worklist(BLeafs.begin(), BLeafs.end());
+      llvm::DenseMap<ModuleMacro *, unsigned> Visits;
+      while (!Worklist.empty()) {
+        auto *BMacro = Worklist.pop_back_val();
+
+        auto *AModule = translate(BMacro->getOwningModule());
+        auto *AMacroInfo = translate(BMacro->getMacroInfo());
+
+        std::vector<ModuleMacro *> AOverrides;
+        for (auto *BOverride : BMacro->overrides()) {
+          auto *AOverrideModule = translate(BOverride->getOwningModule());
+          AOverrides.push_back(APP.getModuleMacro(AOverrideModule, AName));
+        }
+
+        bool Inserted = false;
+        APP.addModuleMacro(AModule, AName, AMacroInfo, AOverrides, Inserted);
+
+        // Enqueue overridden macros once we've visited all their ancestors.
+        for (auto *BModuleMacro : BMacro->overrides())
+          if (++Visits[BModuleMacro] == BModuleMacro->getNumOverridingMacros())
+            Worklist.push_back(BModuleMacro);
+      }
+    }
+  }
+};
+
+// Copied from ASTWriter.cpp.
+static std::set<const FileEntry *>
+GetAffectingModuleMaps(const HeaderSearch &HS, Module *RootModule) {
+  std::set<const FileEntry *> ModuleMaps{};
+  std::set<const Module *> ProcessedModules;
+  SmallVector<const Module *> ModulesToProcess{RootModule};
+
+  SmallVector<const FileEntry *, 16> FilesByUID;
+  HS.getFileMgr().GetUniqueIDMapping(FilesByUID);
+
+  if (FilesByUID.size() > HS.header_file_size())
+    FilesByUID.resize(HS.header_file_size());
+
+  for (unsigned UID = 0, LastUID = FilesByUID.size(); UID != LastUID; ++UID) {
+    const FileEntry *File = FilesByUID[UID];
+    if (!File)
+      continue;
+
+    const HeaderFileInfo *HFI =
+        HS.getExistingFileInfo(File, /*WantExternal*/ false);
+    if (!HFI || (HFI->isModuleHeader && !HFI->isCompilingModuleHeader))
+      continue;
+
+    for (const auto &KH : HS.findAllModulesForHeader(File)) {
+      if (!KH.getModule())
+        continue;
+      ModulesToProcess.push_back(KH.getModule());
+    }
+  }
+
+  while (!ModulesToProcess.empty()) {
+    auto *CurrentModule = ModulesToProcess.pop_back_val();
+    ProcessedModules.insert(CurrentModule);
+
+    Optional<FileEntryRef> ModuleMapFile =
+        HS.getModuleMap().getModuleMapFileForUniquing(CurrentModule);
+    if (!ModuleMapFile) {
+      continue;
+    }
+
+    ModuleMaps.insert(*ModuleMapFile);
+
+    for (auto *ImportedModule : (CurrentModule)->Imports) {
+      if (!ImportedModule ||
+          ProcessedModules.find(ImportedModule) != ProcessedModules.end()) {
+        continue;
+      }
+      ModulesToProcess.push_back(ImportedModule);
+    }
+
+    for (const Module *UndeclaredModule : CurrentModule->UndeclaredUses)
+      if (UndeclaredModule &&
+          ProcessedModules.find(UndeclaredModule) == ProcessedModules.end())
+        ModulesToProcess.push_back(UndeclaredModule);
+
+    for (const Module *AffectingModule : CurrentModule->AffectingClangModules)
+      if (AffectingModule && ProcessedModules.find(AffectingModule) == ProcessedModules.end())
+        ModulesToProcess.push_back(AffectingModule);
+  }
+
+  return ModuleMaps;
+}
+
 /// Compile a module file for the given module, using the options
 /// provided by the importing compiler instance. Returns true if the module
 /// was built without errors.
 static bool
 compileModuleImpl(CompilerInstance &ImportingInstance, SourceLocation ImportLoc,
                   StringRef ModuleName, FrontendInputFile Input,
                   StringRef OriginalModuleMapFile, StringRef ModuleFileName,
                   llvm::function_ref<void(CompilerInstance &)> PreBuildStep =
compileModuleImpl(CompilerInstance &ImportingInstance, SourceLocation ImportLoc,
   PreBuildStep(Instance);
 
   // Execute the action to actually build the module in-place. Use a separate
   // thread so that we get a stack large enough.
   bool Crashed = !llvm::CrashRecoveryContext().RunSafelyOnThread(
       [&]() {
         GenerateModuleFromModuleMapAction Action;
         Instance.ExecuteAction(Action);
+
+        if (!Instance.getPreprocessorOpts().ScanningMode)
+          return;
+
+        Translator T(ImportingInstance, Instance);
+        T.translateModule(ModuleName);
+        T.translatePreprocessor();
+
+        for (const auto &X : Instance.SearchPathUsage)
+          if (!ImportingInstance.SearchPathUsage.count(X.getKey()))
+            ImportingInstance.SearchPathUsage[X.getKey()] = X.getValue();
+
+        auto &HSUsage = ImportingInstance.SearchPathUsage[ModuleName];
+        for (bool Used : Instance.getPreprocessor()
+                             .getHeaderSearchInfo()
+                             .computeUserEntryUsage())
+          HSUsage.push_back(Used);
+
+        for (const auto &X : Instance.SortedFiles)
+          if (!ImportingInstance.SortedFiles.count(X.getKey())) {
+            ImportingInstance.SortedFiles[X.getKey()] = X.getValue();
+          }
+
+        auto &SortedFiles = ImportingInstance.SortedFiles[ModuleName];
+
+        std::vector<CompilerInstance::EntryStruct> UserFiles;
+        std::vector<CompilerInstance::EntryStruct> SystemFiles;
+
+        std::set<const FileEntry *> AffectingModuleMaps =
+            GetAffectingModuleMaps(
+                Instance.getPreprocessor().getHeaderSearchInfo(),
+                Instance.getPreprocessor().getHeaderSearchInfo().lookupModule(
+                    ModuleName));
+
+        SourceManager &SrcMgr = Instance.getPreprocessor().getSourceManager();
+        unsigned N = SrcMgr.local_sloc_entry_size();
+
+        for (unsigned I = 1; I != N; ++I) {
+          const SrcMgr::SLocEntry *SLoc = &SrcMgr.getLocalSLocEntry(I);
+
+          if (!SLoc->isFile())
+            continue;
+          const SrcMgr::FileInfo &File = SLoc->getFile();
+          const SrcMgr::ContentCache *Cache = &File.getContentCache();
+          if (!Cache->OrigEntry)
+            continue;
+
+          if (!isModuleMap(File.getFileCharacteristic()) ||
+              AffectingModuleMaps.empty() ||
+              AffectingModuleMaps.find(Cache->OrigEntry) !=
+                  AffectingModuleMaps.end()) {
+            CompilerInstance::EntryStruct Entry{
+                T.translate(Cache->OrigEntry),
+                isSystem(File.getFileCharacteristic()),
+                isModuleMap(File.getFileCharacteristic()) &&
+                    File.getIncludeLoc().isInvalid()};
+
+            Entry.FE->getName();
+
+            if (Entry.IsSystemFile)
+              SystemFiles.push_back(Entry);
+            else
+              UserFiles.push_back(Entry);
+          }
+        }
+
+        SortedFiles.insert(SortedFiles.end(), UserFiles.begin(), UserFiles.end());
+        SortedFiles.insert(SortedFiles.end(), SystemFiles.begin(), SystemFiles.end());
       },
       DesiredStackSize);
 
   PostBuildStep(Instance);
 
   ImportingInstance.getDiagnostics().Report(ImportLoc,
                                             diag::remark_module_build_done)
     << ModuleName;

 }
 
 /// Read the AST right after compiling the module.
 static bool readASTAfterCompileModule(CompilerInstance &ImportingInstance,
                                       SourceLocation ImportLoc,
                                       SourceLocation ModuleNameLoc,
                                       Module *Module, StringRef ModuleFileName,
                                       bool *OutOfDate) {
+  // Do not attempt to read the AST file.
+  if (ImportingInstance.getPreprocessorOpts().ScanningMode)
+    return true;
+
   DiagnosticsEngine &Diags = ImportingInstance.getDiagnostics();
 
   unsigned ModuleLoadCapabilities = ASTReader::ARR_Missing;
   if (OutOfDate)
     ModuleLoadCapabilities |= ASTReader::ARR_OutOfDate;
 
   // Try to read the module file, now that we've compiled it.
   ASTReader::ASTReadResult ReadResult =
for (unsigned I = 1, N = Path.size(); I != N; ++I) {
     }
 
     Module = Sub;
   }
 
   // Make the named module visible, if it's not already part of the module
   // we are parsing.
   if (ModuleName != getLangOpts().CurrentModule) {
-    if (!Module->IsFromModuleFile && !MapPrivateSubModToTopLevel) {
+    if (!getPreprocessorOpts().ScanningMode && !Module->IsFromModuleFile && !MapPrivateSubModToTopLevel) {
       // We have an umbrella header or directory that doesn't actually include
       // all of the headers within the directory it covers. Complain about
       // this missing submodule and recover by forgetting that we ever saw
       // this submodule.
       // FIXME: Should we detect this at module load time? It seems fairly
       // expensive (and rare).
       getDiagnostics().Report(ImportLoc, diag::warn_missing_submodule)
         << Module->getFullModuleName()

clang/lib/Frontend/FrontendActions.cpp

 
 std::unique_ptr<ASTConsumer>
 ASTViewAction::CreateASTConsumer(CompilerInstance &CI, StringRef InFile) {
   return CreateASTViewer();
 }
 
 std::unique_ptr<ASTConsumer>
 GeneratePCHAction::CreateASTConsumer(CompilerInstance &CI, StringRef InFile) {
+  if (CI.getPreprocessorOpts().ScanningMode)
+    return std::make_unique<ASTConsumer>();
+
   std::string Sysroot;
   if (!ComputeASTConsumerArguments(CI, /*ref*/ Sysroot))
     return nullptr;
 
   std::string OutputFile;
   std::unique_ptr<raw_pwrite_stream> OS =
       CreateOutputFile(CI, InFile, /*ref*/ OutputFile);
   if (!OS)

 bool GeneratePCHAction::BeginSourceFileAction(CompilerInstance &CI) {
   CI.getLangOpts().CompilingPCH = true;
   return true;
 }
 
 std::unique_ptr<ASTConsumer>
 GenerateModuleAction::CreateASTConsumer(CompilerInstance &CI,
                                         StringRef InFile) {
+  if (CI.getPreprocessorOpts().ScanningMode)
+    return std::make_unique<ASTConsumer>();
+
   std::unique_ptr<raw_pwrite_stream> OS = CreateOutputFile(CI, InFile);
   if (!OS)
     return nullptr;
 
   std::string OutputFile = CI.getFrontendOpts().OutputFile;
   std::string Sysroot;
 
   auto Buffer = std::make_shared<PCHBuffer>();

clang/lib/Serialization/ASTWriter.cpp

for (auto *ImportedModule : (CurrentModule)->Imports) {
       }
       ModulesToProcess.push_back(ImportedModule);
     }
 
     for (const Module *UndeclaredModule : CurrentModule->UndeclaredUses)
       if (UndeclaredModule &&
           ProcessedModules.find(UndeclaredModule) == ProcessedModules.end())
         ModulesToProcess.push_back(UndeclaredModule);
+
+    for (const Module *AffectingModule : CurrentModule->AffectingClangModules)
+      if (AffectingModule && ProcessedModules.find(AffectingModule) == ProcessedModules.end())
+        ModulesToProcess.push_back(AffectingModule);
   }
 
   return ModuleMaps;
 }
 
 class ASTTypeWriter {
   ASTWriter &Writer;
   ASTWriter::RecordData Record;

clang/lib/Serialization/GeneratePCH.cpp

 //===--- GeneratePCH.cpp - Sema Consumer for PCH Generation -----*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines the PCHGenerator, which as a SemaConsumer that generates
 //  a PCH file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/ASTContext.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
+#include "clang/Lex/PreprocessorOptions.h"
 #include "clang/Sema/SemaConsumer.h"
 #include "clang/Serialization/ASTWriter.h"
 #include "llvm/Bitstream/BitstreamWriter.h"
 
 using namespace clang;
 
 PCHGenerator::PCHGenerator(
     const Preprocessor &PP, InMemoryModuleCache &ModuleCache,
: PP(PP), OutputFile(OutputFile), isysroot(isysroot.str()),
       ShouldCacheASTInMemory(ShouldCacheASTInMemory) {
   this->Buffer->IsComplete = false;
 }
 
 PCHGenerator::~PCHGenerator() {
 }
 
 void PCHGenerator::HandleTranslationUnit(ASTContext &Ctx) {
+  // Do not attempt to write the AST file.
+  if (PP.getPreprocessorOpts().ScanningMode)
+    return;
+
   // Don't create a PCH if there were fatal failures during module loading.
   if (PP.getModuleLoader().HadFatalFailure)
     return;
 
   bool hasErrors = PP.getDiagnostics().hasErrorOccurred();
   if (hasErrors && !AllowASTWithErrors)
     return;
 

clang/lib/Tooling/DependencyScanning/DependencyScanningService.cpp

 //===- DependencyScanningService.cpp - clang-scan-deps service ------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/DependencyScanning/DependencyScanningService.h"
-#include "llvm/Support/TargetSelect.h"
 
 using namespace clang;
 using namespace tooling;
 using namespace dependencies;
 
 DependencyScanningService::DependencyScanningService(
     ScanningMode Mode, ScanningOutputFormat Format, bool OptimizeArgs,
     bool EagerLoadModules)
     : Mode(Mode), Format(Format), OptimizeArgs(OptimizeArgs),
-      EagerLoadModules(EagerLoadModules) {
-  // Initialize targets for object file support.
-  llvm::InitializeAllTargets();
-  llvm::InitializeAllTargetMCs();
-  llvm::InitializeAllAsmPrinters();
-  llvm::InitializeAllAsmParsers();
-}
+      EagerLoadModules(EagerLoadModules) {}

clang/lib/Tooling/DependencyScanning/DependencyScanningWorker.cpp

bool runInvocation(std::shared_ptr<CompilerInvocation> Invocation,
 
     Scanned = true;
 
     // Create a compiler instance to handle the actual work.
     ScanInstanceStorage.emplace(std::move(PCHContainerOps));
     CompilerInstance &ScanInstance = *ScanInstanceStorage;
     ScanInstance.setInvocation(std::move(Invocation));
 
+    ScanInstance.getFrontendOpts().BuildingImplicitModuleUsesLock = false;
+    ScanInstance.getPreprocessorOpts().ScanningMode = true;
+
     // Create the compiler's actual diagnostics engine.
     sanitizeDiagOpts(ScanInstance.getDiagnosticOpts());
     ScanInstance.createDiagnostics(DiagConsumer, /*ShouldOwnClient=*/false);
     if (!ScanInstance.hasDiagnostics())
       return false;
 
     ScanInstance.getPreprocessorOpts().AllowPCHWithDifferentModulesCachePath =
         true;

clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp

 #include "clang/Tooling/DependencyScanning/DependencyScanningWorker.h"
 #include "llvm/Support/BLAKE3.h"
 #include "llvm/Support/StringSaver.h"
 
 using namespace clang;
 using namespace tooling;
 using namespace dependencies;
 
-static void optimizeHeaderSearchOpts(HeaderSearchOptions &Opts,
-                                     ASTReader &Reader,
-                                     const serialization::ModuleFile &MF) {
+static void optimizeHeaderSearchOpts(HeaderSearchOptions &Opts, const Module *M,
+                                     CompilerInstance &CI) {
   // Only preserve search paths that were used during the dependency scan.
   std::vector<HeaderSearchOptions::Entry> Entries = Opts.UserEntries;
   Opts.UserEntries.clear();
 
   llvm::BitVector SearchPathUsage(Entries.size());
-  llvm::DenseSet<const serialization::ModuleFile *> Visited;
-  std::function<void(const serialization::ModuleFile *)> VisitMF =
-      [&](const serialization::ModuleFile *MF) {
-        SearchPathUsage |= MF->SearchPathUsage;
-        Visited.insert(MF);
-        for (const serialization::ModuleFile *Import : MF->Imports)
-          if (!Visited.contains(Import))
-            VisitMF(Import);
-      };
-  VisitMF(&MF);
+  llvm::DenseSet<const Module *> Visited;
+  std::function<void(const Module *)> VisitM = [&](const Module *M) {
+    SearchPathUsage |= CI.SearchPathUsage[M->getTopLevelModuleName()];
+    Visited.insert(M);
+    for (const Module *Import : M->Imports)
+        VisitM(Import);
+  VisitM(M);
 
   for (auto Idx : SearchPathUsage.set_bits())
     Opts.UserEntries.push_back(Entries[Idx]);
 }
 
 static std::vector<std::string> splitString(std::string S, char Separator) {
   SmallVector<StringRef> Segments;
   StringRef(S).split(Segments, Separator, /*MaxSplit=*/-1, /*KeepEmpty=*/false);
for (const Module *M :
     if (!MDC.isPrebuiltModule(M))
       DirectModularDeps.insert(M);
 
   for (const Module *M : DirectModularDeps) {
     // A top-level module might not be actually imported as a module when
     // -fmodule-name is used to compile a translation unit that imports this
     // module. In that case it can be skipped. The appropriate header
     // dependencies will still be reported as expected.
-    if (!M->getASTFile())
+    if (M->getFullModuleName() == MDC.ScanInstance.getLangOpts().ModuleName)
       continue;
     handleTopLevelModule(M);
   }
 
   MDC.Consumer.handleDependencyOutputOpts(*MDC.Opts);
 
   for (auto &&I : MDC.ModularDeps)
     MDC.Consumer.handleModuleDependency(*I.second);
ModuleID ModuleDepCollectorPP::handleTopLevelModule(const Module *M) {
   if (!ModI.second)
     return ModI.first->second->ID;
 
   ModI.first->second = std::make_unique<ModuleDeps>();
   ModuleDeps &MD = *ModI.first->second;
 
   MD.ID.ModuleName = M->getFullModuleName();
   MD.ImportedByMainFile = DirectModularDeps.contains(M);
-  MD.ImplicitModulePCMPath = std::string(M->getASTFile()->getName());
   MD.IsSystem = M->IsSystem;
 
   ModuleMap &ModMapInfo =
       MDC.ScanInstance.getPreprocessor().getHeaderSearchInfo().getModuleMap();
 
   Optional<FileEntryRef> ModuleMap = ModMapInfo.getModuleMapFileForUniquing(M);
 
   if (ModuleMap) {
     SmallString<128> Path = ModuleMap->getNameAsRequested();
     ModMapInfo.canonicalizeModuleMapPath(Path);
     MD.ClangModuleMapFile = std::string(Path);
   }
 
-  serialization::ModuleFile *MF =
-      MDC.ScanInstance.getASTReader()->getModuleManager().lookup(
-          M->getASTFile());
-  MDC.ScanInstance.getASTReader()->visitInputFiles(
-      *MF, true, true, [&](const serialization::InputFile &IF, bool isSystem) {
-        // __inferred_module.map is the result of the way in which an implicit
-        // module build handles inferred modules. It adds an overlay VFS with
-        // this file in the proper directory and relies on the rest of Clang to
-        // handle it like normal. With explicitly built modules we don't need
-        // to play VFS tricks, so replace it with the correct module map.
-        if (IF.getFile()->getName().endswith("__inferred_module.map")) {
-          MDC.addFileDep(MD, ModuleMap->getName());
-          return;
-        }
-        MDC.addFileDep(MD, IF.getFile()->getName());
-      });
+  for (const auto &E : MDC.ScanInstance.SortedFiles[M->getFullModuleName()]) {
+    if (E.FE->getName().endswith("__inferred_module.map")) {
+      continue;
+    }
+    MDC.addFileDep(MD, E.FE->getName());
 
   llvm::DenseSet<const Module *> SeenDeps;
   addAllSubmodulePrebuiltDeps(M, MD, SeenDeps);
   addAllSubmoduleDeps(M, MD, SeenDeps);
   addAllAffectingClangModules(M, MD, SeenDeps);
 
-  MDC.ScanInstance.getASTReader()->visitTopLevelModuleMaps(
-      *MF, [&](const FileEntry *FE) {
-        if (FE->getName().endswith("__inferred_module.map"))
-          return;
-        MD.ModuleMapFileDeps.emplace_back(FE->getName());
-      });
+  for (const auto &E : MDC.ScanInstance.SortedFiles[M->getFullModuleName()]) {
+    if (!E.IsTopLevelModuleMap)
+      continue;
+    if (E.FE->getName().endswith("__inferred_module.map"))
+      continue;
+    MD.ModuleMapFileDeps.emplace_back(E.FE->getName());
+  }
 
   CompilerInvocation CI = MDC.makeInvocationForModuleBuildWithoutOutputs(
       MD, [&](CompilerInvocation &BuildInvocation) {
         if (MDC.OptimizeArgs)
-          optimizeHeaderSearchOpts(BuildInvocation.getHeaderSearchOpts(),
-                                   *MDC.ScanInstance.getASTReader(), *MF);
+          optimizeHeaderSearchOpts(BuildInvocation.getHeaderSearchOpts(), M,
+                                   MDC.ScanInstance);
       });
 
   MDC.associateWithContextHash(CI, MD);
 
   // Finish the compiler invocation. Requires dependencies and the context hash.
   MDC.addOutputPaths(CI, MD);
 
   MD.BuildArguments = CI.getCC1CommandLine();

clang/test/ClangScanDeps/modules-basic.c

+// RUN: rm -rf %t
+// RUN: split-file %s %t
+
+//--- include/module.modulemap
+module top { header "top.h" }
+module left { header "left.h" }
+module right { header "right.h" }
+module right_extra { header "right-extra.h" }
+module bottom { header "bottom.h" }
+//--- include/top.h
+//
+#define D1
+//--- include/left.h
+///
+#include "top.h"
+#define D2
+//--- include/right.h
+////
+#include "right-extra.h"
+#include "top.h"
+#define D3
+//--- include/right-extra.h
+/////
+#define D4
+//--- include/bottom.h
+//////
+#include "left.h"
+#include "right.h"
+#define D5
+//--- include/t.h
+
+//--- tu.c
+#include "bottom.h"
+#ifdef D1
+#endif
+#ifdef D2
+#endif
+#ifdef D3
+#endif
+#ifdef D4
+#endif
+#ifdef D5
+#endif
+
+#define D1
+#define D2
+#define D3
+#define D4
+#define D5
+
+//--- cdb.json.template
+[{
+  "file": "DIR/tu.c",
+  "directory": "DIR",
+  "command": "clang -fsyntax-only DIR/tu.c -fmodules -fmodules-cache-path=DIR/cache -fimplicit-module-maps -I DIR/include"
+}]
+
+// 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 %s -DPREFIX=%/t
+
+// CHECK: {
+// CHECK-NEXT:   "modules": [
+// CHECK-NEXT:     {
+// CHECK-NEXT:       clang-module-deps": [
+// CHECK-NEXT:        {
+// CHECK-NEXT:          "context-hash": "[[X_HASH:.*]]",
+// CHECK-NEXT:          "module-name": "x"
+// CHECK-NEXT:        }
+// CHECK-NEXT:       ],
+// CHECK-NEXT:       "clang-modulemap-file": "[[PREFIX]]/include/module.modulemap",
+// CHECK-NEXT:       "command-line": [
+// CHECK-NEXT:         "-cc1",
+// CHECK:              "-o",
+// CHECK-NEXT:         "[[PREFIX]]/cache/{{.*}}/m-{{.*}}.pcm",
+// CHECK:              "-emit-module",
+// CHECK:              "[[PREFIX]]/include/module.modulemap",
+// CHECK:              "-fmodules",
+// CHECK:              "-fmodule-name=m",
+// CHECK:            ],
+// CHECK-NEXT:       "context-hash": "[[M_HASH:.*]]",
+// CHECK-NEXT:       "file-deps": [
+// CHECK-NEXT:         "[[PREFIX]]/include/m.h",
+// CHECK-NEXT:         "[[PREFIX]]/include/module.modulemap"
+// CHECK-NEXT:       ],
+// CHECK-NEXT:       "name": "m"
+// CHECK-NEXT:     },
+// CHECK-NEXT:     {
+// CHECK-NEXT:       "clang-module-deps": [],
+// CHECK-NEXT:       "clang-modulemap-file": "[[PREFIX]]/include/module.modulemap",
+// CHECK-NEXT:       "command-line": [
+// CHECK-NEXT:         "-cc1",
+// CHECK:              "-o",
+// CHECK-NEXT:         "[[PREFIX]]/cache/{{.*}}/x-{{.*}}.pcm",
+// CHECK:              "-emit-module",
+// CHECK:              "[[PREFIX]]/include/module.modulemap",
+// CHECK:              "-fmodules",
+// CHECK:              "-fmodule-name=x",
+// CHECK:            ],
+// CHECK-NEXT:       "context-hash": "[[X_HASH]]",
+// CHECK-NEXT:        "file-deps": [
+// CHECK-NEXT:          "[[PREFIX]]/include/module.modulemap",
+// CHECK-NEXT:          "[[PREFIX]]/include/x.h"
+// CHECK-NEXT:        ],
+// CHECK-NEXT:       "name": "x"
+// CHECK-NEXT:     }
+// CHECK-NEXT:   ],
+// CHECK-NEXT:   "translation-units": [
+// CHECK-NEXT:     {
+// CHECK-NEXT:       "commands": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "clang-context-hash": "{{.*}}",
+// CHECK-NEXT:           "clang-module-deps": [
+// CHECK-NEXT:             {
+// CHECK-NEXT:               "context-hash": "[[M_HASH]]",
+// CHECK-NEXT:               "module-name": "m"
+// CHECK-NEXT:             }
+// CHECK-NEXT:           ],
+// CHECK-NEXT:           "command-line": [
+// CHECK-NEXT:             "-cc1",
+// CHECK:                  "-fmodule-map-file=[[PREFIX]]/include/module.modulemap",
+// CHECK:                  "-fmodule-file=m=[[PREFIX]]/cache/{{.*}}/m-{{.*}}.pcm",
+// CHECK:                ],
+// CHECK-NEXT:           "executable": "clang",
+// CHECK-NEXT:           "file-deps": [
+// CHECK-NEXT:             "[[PREFIX]]/tu.c",
+// CHECK-NEXT:             "[[PREFIX]]/include/t.h"
+// CHECK-NEXT:           ],
+// CHECK-NEXT:           "input-file": "[[PREFIX]]/tu.c"
+// CHECK-NEXT:         }
+// CHECK-NEXT:       ]
+// CHECK-NEXT:     }
+// CHECK-NEXT:   ]
+// CHECK-NEXT: }