//===- ModuleDepCollector.cpp - Callbacks to collect deps -------*- 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
//
//===----------------------------------------------------------------------===//

#include "clang/DependencyScanning/ModuleDepCollector.h"

#include "clang/Basic/MakeSupport.h"
#include "clang/DependencyScanning/DependencyActionController.h"
#include "clang/DependencyScanning/DependencyConsumer.h"
#include "clang/DependencyScanning/DependencyScanningWorker.h"
#include "clang/Frontend/CompilerInstance.h"
#include "clang/Lex/Preprocessor.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/BLAKE3.h"
#include <optional>

using namespace clang;
using namespace dependencies;

static PrebuiltModuleDep
createPrebuiltModuleDep(const serialization::ModuleFile *MF) {
  PrebuiltModuleDep Dep;
  Dep.ModuleName = MF->ModuleName;
  Dep.PCMFile = MF->FileName.str();
  Dep.ModuleMapFile = MF->ModuleMapPath;
  return Dep;
}

void PrebuiltModuleASTAttrs::updateDependentsNotInStableDirs(
    PrebuiltModulesAttrsMap &PrebuiltModulesMap) {
  setInStableDir();
  for (const auto Dep : ModuleFileDependents) {
    if (!PrebuiltModulesMap[Dep].isInStableDir())
      return;
    PrebuiltModulesMap[Dep].updateDependentsNotInStableDirs(PrebuiltModulesMap);
  }
}

static void
optimizeHeaderSearchOpts(HeaderSearchOptions &Opts, ASTReader &Reader,
                         const serialization::ModuleFile &MF,
                         const PrebuiltModulesAttrsMap &PrebuiltModulesASTMap,
                         ScanningOptimizations OptimizeArgs) {
  if (any(OptimizeArgs & ScanningOptimizations::HeaderSearch)) {
    // Only preserve search paths that were used during the dependency scan.
    std::vector<HeaderSearchOptions::Entry> Entries;
    std::swap(Opts.UserEntries, Entries);

    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);

    if (SearchPathUsage.size() != Entries.size())
      llvm::report_fatal_error(
          "Inconsistent search path options between modules detected");

    for (auto Idx : SearchPathUsage.set_bits())
      Opts.UserEntries.push_back(std::move(Entries[Idx]));
  }
  if (any(OptimizeArgs & ScanningOptimizations::VFS)) {
    std::vector<std::string> VFSOverlayFiles;
    std::swap(Opts.VFSOverlayFiles, VFSOverlayFiles);

    llvm::BitVector VFSUsage(VFSOverlayFiles.size());
    llvm::DenseSet<const serialization::ModuleFile *> Visited;
    std::function<void(const serialization::ModuleFile *)> VisitMF =
        [&](const serialization::ModuleFile *MF) {
          Visited.insert(MF);
          if (MF->Kind == serialization::MK_ImplicitModule) {
            VFSUsage |= MF->VFSUsage;
            // We only need to recurse into implicit modules. Other module types
            // will have the correct set of VFSs for anything they depend on.
            for (const serialization::ModuleFile *Import : MF->Imports)
              if (!Visited.contains(Import))
                VisitMF(Import);
          } else {
            // This is not an implicitly built module, so it may have different
            // VFS options. Fall back to a string comparison instead.
            auto PrebuiltModulePropIt =
                PrebuiltModulesASTMap.find(MF->FileName);
            if (PrebuiltModulePropIt == PrebuiltModulesASTMap.end())
              return;
            for (std::size_t I = 0, E = VFSOverlayFiles.size(); I != E; ++I) {
              if (PrebuiltModulePropIt->second.getVFS().contains(
                      VFSOverlayFiles[I]))
                VFSUsage[I] = true;
            }
          }
        };
    VisitMF(&MF);

    if (VFSUsage.size() != VFSOverlayFiles.size())
      llvm::report_fatal_error(
          "Inconsistent -ivfsoverlay options between modules detected");

    for (auto Idx : VFSUsage.set_bits())
      Opts.VFSOverlayFiles.push_back(std::move(VFSOverlayFiles[Idx]));
  }
}

static void optimizeDiagnosticOpts(DiagnosticOptions &Opts,
                                   bool IsSystemModule) {
  // If this is not a system module or -Wsystem-headers was passed, don't
  // optimize.
  if (!IsSystemModule)
    return;
  bool Wsystem_headers = false;
  for (StringRef Opt : Opts.Warnings) {
    bool isPositive = !Opt.consume_front("no-");
    if (Opt == "system-headers")
      Wsystem_headers = isPositive;
  }
  if (Wsystem_headers)
    return;

  // Remove all warning flags. System modules suppress most, but not all,
  // warnings.
  Opts.Warnings.clear();
  Opts.UndefPrefixes.clear();
  Opts.Remarks.clear();
}

static void optimizeCWD(CowCompilerInvocation &BuildInvocation, StringRef CWD) {
  BuildInvocation.getMutFileSystemOpts().WorkingDir.clear();
  BuildInvocation.getMutCodeGenOpts().DebugCompilationDir.clear();
  BuildInvocation.getMutCodeGenOpts().CoverageCompilationDir.clear();
}

static std::vector<std::string> splitString(std::string S, char Separator) {
  SmallVector<StringRef> Segments;
  StringRef(S).split(Segments, Separator, /*MaxSplit=*/-1, /*KeepEmpty=*/false);
  std::vector<std::string> Result;
  Result.reserve(Segments.size());
  for (StringRef Segment : Segments)
    Result.push_back(Segment.str());
  return Result;
}

void ModuleDepCollector::addOutputPaths(CowCompilerInvocation &CI,
                                        ModuleDeps &Deps) {
  CI.getMutFrontendOpts().OutputFile =
      Controller.lookupModuleOutput(Deps, ModuleOutputKind::ModuleFile);
  if (!CI.getDiagnosticOpts().DiagnosticSerializationFile.empty())
    CI.getMutDiagnosticOpts().DiagnosticSerializationFile =
        Controller.lookupModuleOutput(
            Deps, ModuleOutputKind::DiagnosticSerializationFile);
  if (!CI.getDependencyOutputOpts().OutputFile.empty()) {
    CI.getMutDependencyOutputOpts().OutputFile =
        Controller.lookupModuleOutput(Deps, ModuleOutputKind::DependencyFile);
    CI.getMutDependencyOutputOpts().Targets =
        splitString(Controller.lookupModuleOutput(
                        Deps, ModuleOutputKind::DependencyTargets),
                    '\0');
    if (!CI.getDependencyOutputOpts().OutputFile.empty() &&
        CI.getDependencyOutputOpts().Targets.empty()) {
      // Fallback to -o as dependency target, as in the driver.
      SmallString<128> Target;
      quoteMakeTarget(CI.getFrontendOpts().OutputFile, Target);
      CI.getMutDependencyOutputOpts().Targets.push_back(std::string(Target));
    }
  }
}

void dependencies::resetBenignCodeGenOptions(frontend::ActionKind ProgramAction,
                                             const LangOptions &LangOpts,
                                             CodeGenOptions &CGOpts) {
  // TODO: Figure out better way to set options to their default value.
  if (ProgramAction == frontend::GenerateModule) {
    CGOpts.MainFileName.clear();
    CGOpts.DwarfDebugFlags.clear();
  }
  if (ProgramAction == frontend::GeneratePCH ||
      (ProgramAction == frontend::GenerateModule && !LangOpts.ModulesCodegen)) {
    CGOpts.DebugCompilationDir.clear();
    CGOpts.CoverageCompilationDir.clear();
    CGOpts.CoverageDataFile.clear();
    CGOpts.CoverageNotesFile.clear();
    CGOpts.ProfileInstrumentUsePath.clear();
    CGOpts.SampleProfileFile.clear();
    CGOpts.ProfileRemappingFile.clear();
  }
}

bool dependencies::isPathInStableDir(const ArrayRef<StringRef> Directories,
                                     const StringRef Input) {
  using namespace llvm::sys;

  if (!path::is_absolute(Input))
    return false;

  auto PathStartsWith = [](StringRef Prefix, StringRef Path) {
    auto PrefixIt = path::begin(Prefix), PrefixEnd = path::end(Prefix);
    for (auto PathIt = path::begin(Path), PathEnd = path::end(Path);
         PrefixIt != PrefixEnd && PathIt != PathEnd; ++PrefixIt, ++PathIt) {
      if (*PrefixIt != *PathIt)
        return false;
    }
    return PrefixIt == PrefixEnd;
  };

  return any_of(Directories, [&](StringRef Dir) {
    return !Dir.empty() && PathStartsWith(Dir, Input);
  });
}

bool dependencies::areOptionsInStableDir(const ArrayRef<StringRef> Directories,
                                         const HeaderSearchOptions &HSOpts) {
  assert(isPathInStableDir(Directories, HSOpts.Sysroot) &&
         "Sysroots differ between module dependencies and current TU");

  assert(isPathInStableDir(Directories, HSOpts.ResourceDir) &&
         "ResourceDirs differ between module dependencies and current TU");

  for (const auto &Entry : HSOpts.UserEntries) {
    if (!Entry.IgnoreSysRoot)
      continue;
    if (!isPathInStableDir(Directories, Entry.Path))
      return false;
  }

  for (const auto &SysPrefix : HSOpts.SystemHeaderPrefixes) {
    if (!isPathInStableDir(Directories, SysPrefix.Prefix))
      return false;
  }

  return true;
}

static CowCompilerInvocation
makeCommonInvocationForModuleBuild(CompilerInvocation CI) {
  CI.resetNonModularOptions();
  CI.clearImplicitModuleBuildOptions();

  // The scanner takes care to avoid passing non-affecting module maps to the
  // explicit compiles. No need to do extra work just to find out there are no
  // module map files to prune.
  CI.getHeaderSearchOpts().ModulesPruneNonAffectingModuleMaps = false;

  // Remove options incompatible with explicit module build or are likely to
  // differ between identical modules discovered from different translation
  // units.
  CI.getFrontendOpts().Inputs.clear();
  CI.getFrontendOpts().OutputFile.clear();
  CI.getFrontendOpts().GenReducedBMI = false;
  CI.getFrontendOpts().ModuleOutputPath.clear();
  CI.getHeaderSearchOpts().ModulesSkipHeaderSearchPaths = false;
  CI.getHeaderSearchOpts().ModulesSkipDiagnosticOptions = false;
  // LLVM options are not going to affect the AST
  CI.getFrontendOpts().LLVMArgs.clear();

  resetBenignCodeGenOptions(frontend::GenerateModule, CI.getLangOpts(),
                            CI.getCodeGenOpts());

  // Erase the command-line arguments. These don't make it into the final set of
  // compilation arguments and will be re-populated during compilation itself.
  // Keeping them around would make copies of the invocation expensive.
  CI.getCodeGenOpts().Argv0 = nullptr;
  CI.getCodeGenOpts().CommandLineArgs.clear();

  // Map output paths that affect behaviour to "-" so their existence is in the
  // context hash. The final path will be computed in addOutputPaths.
  if (!CI.getDiagnosticOpts().DiagnosticSerializationFile.empty())
    CI.getDiagnosticOpts().DiagnosticSerializationFile = "-";
  if (!CI.getDependencyOutputOpts().OutputFile.empty())
    CI.getDependencyOutputOpts().OutputFile = "-";
  CI.getDependencyOutputOpts().Targets.clear();
  CI.getDependencyOutputOpts().IncludeModuleFiles = MFDK_Direct;

  CI.getFrontendOpts().ProgramAction = frontend::GenerateModule;
  CI.getLangOpts().ModuleName.clear();

  // Remove any macro definitions that are explicitly ignored.
  if (!CI.getHeaderSearchOpts().ModulesIgnoreMacros.empty()) {
    llvm::erase_if(
        CI.getPreprocessorOpts().Macros,
        [&CI](const std::pair<std::string, bool> &Def) {
          StringRef MacroDef = Def.first;
          return CI.getHeaderSearchOpts().ModulesIgnoreMacros.contains(
              llvm::CachedHashString(MacroDef.split('=').first));
        });
    // Remove the now unused option.
    CI.getHeaderSearchOpts().ModulesIgnoreMacros.clear();
  }

  return CI;
}

CowCompilerInvocation
ModuleDepCollector::getInvocationAdjustedForModuleBuildWithoutOutputs(
    const ModuleDeps &Deps,
    llvm::function_ref<void(CowCompilerInvocation &)> Optimize) const {
  CowCompilerInvocation CI = CommonInvocation;

  CI.getMutLangOpts().ModuleName = Deps.ID.ModuleName;
  CI.getMutFrontendOpts().IsSystemModule = Deps.IsSystem;

  // Inputs
  InputKind ModuleMapInputKind(CI.getFrontendOpts().DashX.getLanguage(),
                               InputKind::Format::ModuleMap);
  CI.getMutFrontendOpts().Inputs.emplace_back(Deps.ClangModuleMapFile,
                                              ModuleMapInputKind);

  auto CurrentModuleMapEntry =
      ScanInstance.getFileManager().getOptionalFileRef(Deps.ClangModuleMapFile);
  assert(CurrentModuleMapEntry && "module map file entry not found");

  // Remove directly passed modulemap files. They will get added back if they
  // were actually used.
  CI.getMutFrontendOpts().ModuleMapFiles.clear();

  auto DepModuleMapFiles = collectModuleMapFiles(Deps.ClangModuleDeps);
  for (StringRef ModuleMapFile : Deps.ModuleMapFileDeps) {
    // TODO: Track these as `FileEntryRef` to simplify the equality check below.
    auto ModuleMapEntry =
        ScanInstance.getFileManager().getOptionalFileRef(ModuleMapFile);
    assert(ModuleMapEntry && "module map file entry not found");

    // 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 (Service.getOpts().EagerLoadModules &&
        DepModuleMapFiles.contains(*ModuleMapEntry))
      continue;

    // Don't report module map file of the current module unless it also
    // describes a dependency (for symmetry).
    if (*ModuleMapEntry == *CurrentModuleMapEntry &&
        !DepModuleMapFiles.contains(*ModuleMapEntry))
      continue;

    CI.getMutFrontendOpts().ModuleMapFiles.emplace_back(ModuleMapFile);
  }

  // Report the prebuilt modules this module uses.
  for (const auto &PrebuiltModule : Deps.PrebuiltModuleDeps)
    CI.getMutFrontendOpts().ModuleFiles.push_back(PrebuiltModule.PCMFile);

  // Add module file inputs from dependencies.
  addModuleFiles(CI, Deps.ClangModuleDeps);

  if (!CI.getDiagnosticOpts().SystemHeaderWarningsModules.empty()) {
    // Apply -Wsystem-headers-in-module for the current module.
    if (llvm::is_contained(CI.getDiagnosticOpts().SystemHeaderWarningsModules,
                           Deps.ID.ModuleName))
      CI.getMutDiagnosticOpts().Warnings.push_back("system-headers");
    // Remove the now unused option(s).
    CI.getMutDiagnosticOpts().SystemHeaderWarningsModules.clear();
  }

  Optimize(CI);

  return CI;
}

llvm::DenseSet<const FileEntry *> ModuleDepCollector::collectModuleMapFiles(
    ArrayRef<ModuleID> ClangModuleDeps) const {
  llvm::DenseSet<const FileEntry *> ModuleMapFiles;
  for (const ModuleID &MID : ClangModuleDeps) {
    ModuleDeps *MD = ModuleDepsByID.lookup(MID);
    assert(MD && "Inconsistent dependency info");
    // TODO: Track ClangModuleMapFile as `FileEntryRef`.
    auto FE = ScanInstance.getFileManager().getOptionalFileRef(
        MD->ClangModuleMapFile);
    assert(FE && "Missing module map file that was previously found");
    ModuleMapFiles.insert(*FE);
  }
  return ModuleMapFiles;
}

void ModuleDepCollector::addModuleMapFiles(
    CompilerInvocation &CI, ArrayRef<ModuleID> ClangModuleDeps) const {
  if (Service.getOpts().EagerLoadModules)
    return; // Only pcm is needed for eager load.

  for (const ModuleID &MID : ClangModuleDeps) {
    ModuleDeps *MD = ModuleDepsByID.lookup(MID);
    assert(MD && "Inconsistent dependency info");
    CI.getFrontendOpts().ModuleMapFiles.push_back(MD->ClangModuleMapFile);
  }
}

void ModuleDepCollector::addModuleFiles(
    CompilerInvocation &CI, ArrayRef<ModuleID> ClangModuleDeps) const {
  for (const ModuleID &MID : ClangModuleDeps) {
    ModuleDeps *MD = ModuleDepsByID.lookup(MID);
    std::string PCMPath =
        Controller.lookupModuleOutput(*MD, ModuleOutputKind::ModuleFile);

    if (Service.getOpts().EagerLoadModules)
      CI.getFrontendOpts().ModuleFiles.push_back(std::move(PCMPath));
    else
      CI.getHeaderSearchOpts().PrebuiltModuleFiles.insert(
          {MID.ModuleName, std::move(PCMPath)});
  }
}

void ModuleDepCollector::addModuleFiles(
    CowCompilerInvocation &CI, ArrayRef<ModuleID> ClangModuleDeps) const {
  for (const ModuleID &MID : ClangModuleDeps) {
    ModuleDeps *MD = ModuleDepsByID.lookup(MID);
    std::string PCMPath =
        Controller.lookupModuleOutput(*MD, ModuleOutputKind::ModuleFile);

    if (Service.getOpts().EagerLoadModules)
      CI.getMutFrontendOpts().ModuleFiles.push_back(std::move(PCMPath));
    else
      CI.getMutHeaderSearchOpts().PrebuiltModuleFiles.insert(
          {MID.ModuleName, std::move(PCMPath)});
  }
}

static bool needsModules(FrontendInputFile FIF) {
  switch (FIF.getKind().getLanguage()) {
  case Language::Unknown:
  case Language::Asm:
  case Language::LLVM_IR:
    return false;
  default:
    return true;
  }
}

void ModuleDepCollector::applyDiscoveredDependencies(CompilerInvocation &CI) {
  CI.clearImplicitModuleBuildOptions();
  resetBenignCodeGenOptions(CI.getFrontendOpts().ProgramAction,
                            CI.getLangOpts(), CI.getCodeGenOpts());
  CI.getDependencyOutputOpts().IncludeModuleFiles = MFDK_Direct;

  if (llvm::any_of(CI.getFrontendOpts().Inputs, needsModules)) {
    Preprocessor &PP = ScanInstance.getPreprocessor();
    if (Module *CurrentModule = PP.getCurrentModuleImplementation())
      if (OptionalFileEntryRef CurrentModuleMap =
              PP.getHeaderSearchInfo()
                  .getModuleMap()
                  .getModuleMapFileForUniquing(CurrentModule))
        CI.getFrontendOpts().ModuleMapFiles.emplace_back(
            CurrentModuleMap->getNameAsRequested());

    SmallVector<ModuleID> DirectDeps;
    for (const auto &KV : ModularDeps)
      if (DirectModularDeps.contains(KV.first))
        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 bool isSafeToIgnoreCWD(const CowCompilerInvocation &CI) {
  // Check if the command line input uses relative paths.
  // It is not safe to ignore the current working directory if any of the
  // command line inputs use relative paths.
  bool AnyRelative = false;
  CI.visitPaths([&](StringRef Path) {
    assert(!AnyRelative && "Continuing path visitation despite relative path");
    AnyRelative |= !Path.empty() && !llvm::sys::path::is_absolute(Path);
    return CowCompilerInvocation::VisitConstResult{/*Terminate=*/AnyRelative};
  });
  return !AnyRelative;
}

static std::string getModuleContextHash(const ModuleDeps &MD,
                                        const CowCompilerInvocation &CI,
                                        bool EagerLoadModules,
                                        llvm::vfs::FileSystem &VFS) {
  llvm::HashBuilder<llvm::TruncatedBLAKE3<16>, llvm::endianness::native>
      HashBuilder;

  // Hash the compiler version and serialization version to ensure the module
  // will be readable.
  HashBuilder.add(getClangFullRepositoryVersion());
  HashBuilder.add(serialization::VERSION_MAJOR, serialization::VERSION_MINOR);
  llvm::ErrorOr<std::string> CWD = VFS.getCurrentWorkingDirectory();
  if (CWD && !MD.IgnoreCWD)
    HashBuilder.add(*CWD);

  // Hash the BuildInvocation without any input files.
  SmallString<0> ArgVec;
  ArgVec.reserve(4096);
  CI.generateCC1CommandLine([&](const Twine &Arg) {
    Arg.toVector(ArgVec);
    ArgVec.push_back('\0');
  });
  HashBuilder.add(ArgVec);

  // Hash the module dependencies. These paths may differ even if the invocation
  // is identical if they depend on the contents of the files in the TU -- for
  // example, case-insensitive paths to modulemap files. Usually such a case
  // would indicate a missed optimization to canonicalize, but it may be
  // difficult to canonicalize all cases when there is a VFS.
  for (const auto &ID : MD.ClangModuleDeps) {
    HashBuilder.add(ID.ModuleName);
    HashBuilder.add(ID.ContextHash);
  }

  HashBuilder.add(EagerLoadModules);

  llvm::BLAKE3Result<16> Hash = HashBuilder.final();
  std::array<uint64_t, 2> Words;
  static_assert(sizeof(Hash) == sizeof(Words), "Hash must match Words");
  std::memcpy(Words.data(), Hash.data(), sizeof(Hash));
  return toString(llvm::APInt(sizeof(Words) * 8, Words), 36, /*Signed=*/false);
}

void ModuleDepCollector::associateWithContextHash(
    const CowCompilerInvocation &CI, ModuleDeps &Deps) {
  Deps.ID.ContextHash =
      getModuleContextHash(Deps, CI, Service.getOpts().EagerLoadModules,
                           ScanInstance.getVirtualFileSystem());
  bool Inserted = ModuleDepsByID.insert({Deps.ID, &Deps}).second;
  (void)Inserted;
  assert(Inserted && "duplicate module mapping");
}

/// Callback that records textual includes and direct modular includes/imports
/// during preprocessing.
class ModuleDepCollector::ModuleDepCollectorPP final : public PPCallbacks {
  /// The parent dependency collector.
  ModuleDepCollector &MDC;

public:
  ModuleDepCollectorPP(ModuleDepCollector &MDC) : MDC(MDC) {}

  void LexedFileChanged(FileID FID, LexedFileChangeReason Reason,
                        SrcMgr::CharacteristicKind FileType, FileID PrevFID,
                        SourceLocation Loc) override {
    if (Reason != LexedFileChangeReason::EnterFile)
      return;

    SourceManager &SM = MDC.ScanInstance.getSourceManager();

    // Dependency generation really does want to go all the way to the
    // file entry for a source location to find out what is depended on.
    // We do not want #line markers to affect dependency generation!
    if (std::optional<StringRef> Filename = SM.getNonBuiltinFilenameForID(FID))
      MDC.addFileDep(llvm::sys::path::remove_leading_dotslash(*Filename));
  }

  void HasInclude(SourceLocation Loc, StringRef FileName, bool IsAngled,
                  OptionalFileEntryRef File,
                  SrcMgr::CharacteristicKind FileType) override {
    if (File)
      MDC.addFileDep(File->getName());
  }

  void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
                          StringRef FileName, bool IsAngled,
                          CharSourceRange FilenameRange,
                          OptionalFileEntryRef File, StringRef SearchPath,
                          StringRef RelativePath, const Module *SuggestedModule,
                          bool ModuleImported,
                          SrcMgr::CharacteristicKind FileType) override {
    if (!File && !ModuleImported) {
      // This is a non-modular include that HeaderSearch failed to find. Add it
      // here as `FileChanged` will never see it.
      MDC.addFileDep(FileName);
    }
    MDC.handleImport(SuggestedModule);
  }

  void moduleImport(SourceLocation ImportLoc, ModuleIdPath Path,
                    const Module *Imported) override {
    auto &PP = MDC.ScanInstance.getPreprocessor();
    if (PP.getLangOpts().CPlusPlusModules && PP.isImportingCXXNamedModules()) {
      P1689ModuleInfo RequiredModule;
      RequiredModule.ModuleName = Path[0].getIdentifierInfo()->getName().str();
      RequiredModule.Type = P1689ModuleInfo::ModuleType::NamedCXXModule;
      MDC.RequiredStdCXXModules.push_back(std::move(RequiredModule));
      return;
    }

    MDC.handleImport(Imported);
  }
};

void ModuleDepCollector::handleImport(const Module *Imported) {
  auto &MDC = *this;

  if (!Imported)
    return;

  const Module *TopLevelModule = Imported->getTopLevelModule();
  const ModuleFileKey *MFKey = TopLevelModule->getASTFileKey();
  if (!MFKey)
    return;
  serialization::ModuleFile *MF =
      MDC.ScanInstance.getASTReader()->getModuleManager().lookup(*MFKey);

  if (MDC.isPrebuiltModule(MF))
    MDC.DirectPrebuiltModularDeps.insert({MF, createPrebuiltModuleDep(MF)});
  else {
    MDC.DirectModularDeps.insert(MF);
    MDC.DirectImports.insert(Imported);
  }
}

void ModuleDepCollector::run(DependencyConsumer &Consumer) {
  auto &MDC = *this;

  FileID MainFileID = MDC.ScanInstance.getSourceManager().getMainFileID();
  MDC.MainFile = std::string(MDC.ScanInstance.getSourceManager()
                                 .getFileEntryRefForID(MainFileID)
                                 ->getName());

  auto &PP = MDC.ScanInstance.getPreprocessor();
  if (PP.isInNamedModule()) {
    P1689ModuleInfo ProvidedModule;
    ProvidedModule.ModuleName = PP.getNamedModuleName();
    ProvidedModule.Type = P1689ModuleInfo::ModuleType::NamedCXXModule;
    ProvidedModule.IsStdCXXModuleInterface = PP.isInNamedInterfaceUnit();
    // Don't put implementation (non partition) unit as Provide.
    // Put the module as required instead. Since the implementation
    // unit will import the primary module implicitly.
    if (PP.isInImplementationUnit())
      MDC.RequiredStdCXXModules.push_back(ProvidedModule);
    else
      MDC.ProvidedStdCXXModule = ProvidedModule;
  }

  if (!MDC.ScanInstance.getPreprocessorOpts().ImplicitPCHInclude.empty())
    MDC.addFileDep(MDC.ScanInstance.getPreprocessorOpts().ImplicitPCHInclude);

  for (StringRef VFS : MDC.ScanInstance.getHeaderSearchOpts().VFSOverlayFiles)
    MDC.addFileDep(VFS);

  if (Module *CurrentModule = PP.getCurrentModuleImplementation()) {
    if (OptionalFileEntryRef CurrentModuleMap =
            PP.getHeaderSearchInfo().getModuleMap().getModuleMapFileForUniquing(
                CurrentModule))
      MDC.addFileDep(CurrentModuleMap->getName());
  }

  for (const Module *M :
       MDC.ScanInstance.getPreprocessor().getAffectingClangModules()) {
    serialization::ModuleFile *MF =
        MDC.ScanInstance.getASTReader()->getModuleManager().lookup(
            *M->getASTFileKey());
    if (!MDC.isPrebuiltModule(MF))
      MDC.DirectModularDeps.insert(MF);
  }

  if (MDC.Service.getOpts().ReportVisibleModules)
    MDC.addVisibleModules();

  for (serialization::ModuleFile *MF : MDC.DirectModularDeps)
    handleTopLevelModule(MF);

  Consumer.handleContextHash(
      MDC.ScanInstance.getInvocation().computeContextHash());

  Consumer.handleDependencyOutputOpts(*MDC.Opts);

  Consumer.handleProvidedAndRequiredStdCXXModules(MDC.ProvidedStdCXXModule,
                                                  MDC.RequiredStdCXXModules);

  for (auto &&I : MDC.ModularDeps)
    Consumer.handleModuleDependency(*I.second);

  for (serialization::ModuleFile *MF : MDC.DirectModularDeps) {
    auto It = MDC.ModularDeps.find(MF);
    // Only report direct dependencies that were successfully handled.
    if (It != MDC.ModularDeps.end())
      Consumer.handleDirectModuleDependency(It->second->ID);
  }

  for (auto &&I : MDC.VisibleModules)
    Consumer.handleVisibleModule(std::string(I.getKey()));

  for (auto &&I : MDC.FileDeps)
    Consumer.handleFileDependency(I);

  for (auto &&I : MDC.DirectPrebuiltModularDeps)
    Consumer.handlePrebuiltModuleDependency(I.second);
}

static StringRef makeAbsoluteAndCanonicalize(CompilerInstance &CI,
                                             StringRef Path,
                                             SmallVectorImpl<char> &Storage) {
  // FIXME: Consider skipping if path is already absolute & canonicalized.

  Storage.assign(Path.begin(), Path.end());
  CI.getFileManager().makeAbsolutePath(Storage, /*Canonicalize=*/true);
  return StringRef(Storage.data(), Storage.size());
}

std::optional<ModuleID>
ModuleDepCollector::handleTopLevelModule(serialization::ModuleFile *MF) {
  auto &MDC = *this;

  // If this module has been handled already, just return its ID.
  if (auto ModI = MDC.ModularDeps.find(MF); ModI != MDC.ModularDeps.end())
    return ModI->second->ID;

  Module *M = MDC.ScanInstance.getPreprocessor()
                  .getHeaderSearchInfo()
                  .getModuleMap()
                  .findModule(MF->ModuleName);
  assert(M && M == M->getTopLevelModule() &&
         "ModuleFile without top-level Module");

  auto OwnedMD = std::make_unique<ModuleDeps>();
  ModuleDeps &MD = *OwnedMD;

  MD.ID.ModuleName = MF->ModuleName;
  MD.IsSystem = M->IsSystem;

  // Start off with the assumption that this module is shareable when there
  // are stable directories. As more dependencies are discovered, check if those
  // come from the provided directories.
  MD.IsInStableDirectories = !MDC.StableDirs.empty();

  // For modules which use export_as link name, the linked product that of the
  // corresponding export_as-named module.
  if (!M->UseExportAsModuleLinkName)
    MD.LinkLibraries = M->LinkLibraries;

  ModuleMap &ModMapInfo =
      MDC.ScanInstance.getPreprocessor().getHeaderSearchInfo().getModuleMap();

  if (auto ModuleMap = ModMapInfo.getModuleMapFileForUniquing(M)) {
    SmallString<128> Path = ModuleMap->getNameAsRequested();
    ModMapInfo.canonicalizeModuleMapPath(Path);
    MD.ClangModuleMapFile = std::string(Path);
  }

  llvm::SmallString<256> Storage;
  MD.FileDepsBaseDir =
      makeAbsoluteAndCanonicalize(MDC.ScanInstance, MF->BaseDirectory, Storage);
  MDC.ScanInstance.getASTReader()->visitInputFileInfos(
      *MF, /*IncludeSystem=*/true,
      [&](const serialization::InputFileInfo &IFI, bool IsSystem) {
        // The __inferred_module.map file is an insignificant implementation
        // detail of implicitly-built modules. The PCM will also report the
        // actual on-disk module map file that allowed inferring the module,
        // which is what we need for building the module explicitly
        // Let's ignore this file.
        if (IFI.UnresolvedImportedFilename.ends_with("__inferred_module.map"))
          return;
        MDC.addFileDep(MD, IFI.UnresolvedImportedFilename);
      });

  addAllModuleDeps(*MF, MD);

  SmallString<0> PathBuf;
  PathBuf.reserve(256);
  MDC.ScanInstance.getASTReader()->visitInputFileInfos(
      *MF, /*IncludeSystem=*/true,
      [&](const serialization::InputFileInfo &IFI, bool IsSystem) {
        if (MD.IsInStableDirectories) {
          auto FullFilePath = ASTReader::ResolveImportedPath(
              PathBuf, IFI.UnresolvedImportedFilename, MF->BaseDirectory);
          MD.IsInStableDirectories =
              isPathInStableDir(MDC.StableDirs, *FullFilePath);
        }
        if (!(IFI.TopLevel && IFI.ModuleMap))
          return;
        if (IFI.UnresolvedImportedFilenameAsRequested.ends_with(
                "__inferred_module.map"))
          return;
        auto ResolvedFilenameAsRequested = ASTReader::ResolveImportedPath(
            PathBuf, IFI.UnresolvedImportedFilenameAsRequested,
            MF->BaseDirectory);
        MD.ModuleMapFileDeps.emplace_back(*ResolvedFilenameAsRequested);
      });

  bool IgnoreCWD = false;
  CowCompilerInvocation CI =
      MDC.getInvocationAdjustedForModuleBuildWithoutOutputs(
          MD, [&](CowCompilerInvocation &BuildInvocation) {
            if (any(MDC.Service.getOpts().OptimizeArgs &
                    (ScanningOptimizations::HeaderSearch |
                     ScanningOptimizations::VFS)))
              optimizeHeaderSearchOpts(BuildInvocation.getMutHeaderSearchOpts(),
                                       *MDC.ScanInstance.getASTReader(), *MF,
                                       MDC.PrebuiltModulesASTMap,
                                       MDC.Service.getOpts().OptimizeArgs);

            if (any(MDC.Service.getOpts().OptimizeArgs &
                    ScanningOptimizations::SystemWarnings))
              optimizeDiagnosticOpts(
                  BuildInvocation.getMutDiagnosticOpts(),
                  BuildInvocation.getFrontendOpts().IsSystemModule);

            IgnoreCWD = any(MDC.Service.getOpts().OptimizeArgs &
                            ScanningOptimizations::IgnoreCWD) &&
                        isSafeToIgnoreCWD(BuildInvocation);
            if (IgnoreCWD) {
              llvm::ErrorOr<std::string> CWD =
                  MDC.ScanInstance.getVirtualFileSystem()
                      .getCurrentWorkingDirectory();
              if (CWD)
                optimizeCWD(BuildInvocation, *CWD);
            }
          });

  // FIXME: Propagate errors up.
  (void)MDC.Controller.finalizeModuleInvocation(MDC.ScanInstance, CI, MD);

  // Check provided input paths from the invocation for determining
  // IsInStableDirectories.
  if (MD.IsInStableDirectories)
    MD.IsInStableDirectories =
        areOptionsInStableDir(MDC.StableDirs, CI.getHeaderSearchOpts());

  MD.IgnoreCWD = IgnoreCWD;
  MDC.associateWithContextHash(CI, MD);

  // Finish the compiler invocation. Requires dependencies and the context hash.
  MDC.addOutputPaths(CI, MD);

  MD.BuildInfo = std::move(CI);

  MDC.ModularDeps.insert({MF, std::move(OwnedMD)});

  return MD.ID;
}

void ModuleDepCollector::addAllModuleDeps(serialization::ModuleFile &MF,
                                          ModuleDeps &MD) {
  auto &MDC = *this;

  llvm::DenseSet<const Module *> Seen;
  for (serialization::ModuleFile *Import : MF.Imports) {
    if (MDC.isPrebuiltModule(Import)) {
      MD.PrebuiltModuleDeps.push_back(createPrebuiltModuleDep(Import));
      if (MD.IsInStableDirectories) {
        auto It = MDC.PrebuiltModulesASTMap.find(
            MD.PrebuiltModuleDeps.back().PCMFile);
        MD.IsInStableDirectories =
            It != MDC.PrebuiltModulesASTMap.end() && It->second.isInStableDir();
      }
    } else {
      if (auto ID = handleTopLevelModule(Import)) {
        MD.ClangModuleDeps.push_back(std::move(*ID));
        if (MD.IsInStableDirectories)
          MD.IsInStableDirectories =
              MDC.ModularDeps[Import]->IsInStableDirectories;
      }
    }
  }
}

ModuleDepCollector::ModuleDepCollector(
    DependencyScanningService &Service,
    std::unique_ptr<DependencyOutputOptions> Opts,
    CompilerInstance &ScanInstance, DependencyActionController &Controller,
    CompilerInvocation OriginalCI,
    const PrebuiltModulesAttrsMap PrebuiltModulesASTMap,
    const ArrayRef<StringRef> StableDirs)
    : Service(Service), ScanInstance(ScanInstance), Controller(Controller),
      PrebuiltModulesASTMap(std::move(PrebuiltModulesASTMap)),
      StableDirs(StableDirs), Opts(std::move(Opts)),
      CommonInvocation(
          makeCommonInvocationForModuleBuild(std::move(OriginalCI))) {}

void ModuleDepCollector::attachToPreprocessor(Preprocessor &PP) {
  auto CollectorPP = std::make_unique<ModuleDepCollectorPP>(*this);
  CollectorPPPtr = CollectorPP.get();
  PP.addPPCallbacks(std::move(CollectorPP));
}

void ModuleDepCollector::attachToASTReader(ASTReader &R) {}

bool ModuleDepCollector::isPrebuiltModule(const serialization::ModuleFile *MF) {
  const auto &PrebuiltModuleFiles =
      ScanInstance.getHeaderSearchOpts().PrebuiltModuleFiles;
  auto PrebuiltModuleFileIt = PrebuiltModuleFiles.find(MF->ModuleName);
  if (PrebuiltModuleFileIt == PrebuiltModuleFiles.end())
    return false;
  assert("Prebuilt module came from the expected AST file" &&
         PrebuiltModuleFileIt->second == MF->FileName.str());
  return true;
}

void ModuleDepCollector::addVisibleModules() {
  llvm::DenseSet<const Module *> ImportedModules;
  auto InsertVisibleModules = [&](const Module *M) {
    if (ImportedModules.contains(M))
      return;

    VisibleModules.insert(M->getTopLevelModuleName());
    SmallVector<Module *> Stack;
    M->getExportedModules(Stack);
    while (!Stack.empty()) {
      const Module *CurrModule = Stack.pop_back_val();
      if (ImportedModules.contains(CurrModule))
        continue;
      ImportedModules.insert(CurrModule);
      VisibleModules.insert(CurrModule->getTopLevelModuleName());
      CurrModule->getExportedModules(Stack);
    }
  };

  for (const Module *Import : DirectImports)
    InsertVisibleModules(Import);
}

void ModuleDepCollector::addFileDep(StringRef Path) {
  if (!Service.getOpts().ReportAbsolutePaths) {
    FileDeps.emplace_back(Path);
    return;
  }

  llvm::SmallString<256> Storage;
  Path = makeAbsoluteAndCanonicalize(ScanInstance, Path, Storage);
  FileDeps.emplace_back(Path);
}

void ModuleDepCollector::addFileDep(ModuleDeps &MD, StringRef Path) {
  MD.FileDeps.emplace_back(Path);
}