//===- HeaderSearch.cpp - Resolve Header File Locations -------------------===//

//

// 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 implements the DirectoryLookup and HeaderSearch interfaces.

//

//===----------------------------------------------------------------------===//

#include "clang/Lex/HeaderSearch.h"

#include "clang/Basic/Diagnostic.h"

#include "clang/Basic/FileManager.h"

#include "clang/Basic/IdentifierTable.h"

#include "clang/Basic/Module.h"

#include "clang/Basic/SourceManager.h"

#include "clang/Lex/DirectoryLookup.h"

#include "clang/Lex/ExternalPreprocessorSource.h"

#include "clang/Lex/HeaderMap.h"

#include "clang/Lex/HeaderSearchOptions.h"

#include "clang/Lex/LexDiagnostic.h"

#include "clang/Lex/ModuleMap.h"

#include "clang/Lex/Preprocessor.h"

#include "llvm/ADT/APInt.h"

#include "llvm/ADT/Hashing.h"

#include "llvm/ADT/SmallString.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/Statistic.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/Support/Allocator.h"

#include "llvm/Support/Capacity.h"

#include "llvm/Support/Errc.h"

#include "llvm/Support/ErrorHandling.h"

#include "llvm/Support/FileSystem.h"

#include "llvm/Support/Path.h"

#include "llvm/Support/VirtualFileSystem.h"

#include <algorithm>

#include <cassert>

#include <cstddef>

#include <cstdio>

#include <cstring>

#include <string>

#include <system_error>

#include <utility>

using namespace clang;

#define DEBUG_TYPE "file-search"

ALWAYS_ENABLED_STATISTIC(NumIncluded, "Number of attempted #includes.");

ALWAYS_ENABLED_STATISTIC(

    NumMultiIncludeFileOptzn,

    "Number of #includes skipped due to the multi-include optimization.");

ALWAYS_ENABLED_STATISTIC(NumFrameworkLookups, "Number of framework lookups.");

ALWAYS_ENABLED_STATISTIC(NumSubFrameworkLookups,

                         "Number of subframework lookups.");

const IdentifierInfo *

HeaderFileInfo::getControllingMacro(ExternalPreprocessorSource *External) {

  if (ControllingMacro) {

    if (ControllingMacro->isOutOfDate()) {

      assert(External && "We must have an external source if we have a "

                         "controlling macro that is out of date.");

      External->updateOutOfDateIdentifier(

          *const_cast<IdentifierInfo *>(ControllingMacro));

    }

    return ControllingMacro;

  }

  if (!ControllingMacroID || 
!External726
)

    return nullptr;

  ControllingMacro = External->GetIdentifier(ControllingMacroID);

  return ControllingMacro;

}

ExternalHeaderFileInfoSource::~ExternalHeaderFileInfoSource() = default;

HeaderSearch::HeaderSearch(std::shared_ptr<HeaderSearchOptions> HSOpts,

                           SourceManager &SourceMgr, DiagnosticsEngine &Diags,

                           const LangOptions &LangOpts,

                           const TargetInfo *Target)

    : HSOpts(std::move(HSOpts)), Diags(Diags),

      FileMgr(SourceMgr.getFileManager()), FrameworkMap(64),

      ModMap(SourceMgr, Diags, LangOpts, Target, *this) {}

void HeaderSearch::PrintStats() {

  llvm::errs() << "\n*** HeaderSearch Stats:\n"

               << FileInfo.size() << " files tracked.\n";

  unsigned NumOnceOnlyFiles = 0;

  for (unsigned i = 0, e = FileInfo.size(); i != e; 
++i151
)

    NumOnceOnlyFiles += (FileInfo[i].isPragmaOnce || FileInfo[i].isImport);

  llvm::errs() << "  " << NumOnceOnlyFiles << " #import/#pragma once files.\n";

  llvm::errs() << "  " << NumIncluded << " #include/#include_next/#import.\n"

               << "    " << NumMultiIncludeFileOptzn

               << " #includes skipped due to the multi-include optimization.\n";

  llvm::errs() << NumFrameworkLookups << " framework lookups.\n"

               << NumSubFrameworkLookups << " subframework lookups.\n";

}

void HeaderSearch::SetSearchPaths(

    std::vector<DirectoryLookup> dirs, unsigned int angledDirIdx,

    unsigned int systemDirIdx, bool noCurDirSearch,

    llvm::DenseMap<unsigned int, unsigned int> searchDirToHSEntry) {

  assert(angledDirIdx <= systemDirIdx && systemDirIdx <= dirs.size() &&

         "Directory indices are unordered");

  SearchDirs = std::move(dirs);

  SearchDirsUsage.assign(SearchDirs.size(), false);

  AngledDirIdx = angledDirIdx;

  SystemDirIdx = systemDirIdx;

  NoCurDirSearch = noCurDirSearch;

  SearchDirToHSEntry = std::move(searchDirToHSEntry);

  //LookupFileCache.clear();

  indexInitialHeaderMaps();

}

void HeaderSearch::AddSearchPath(const DirectoryLookup &dir, bool isAngled) {

  unsigned idx = isAngled ? 
SystemDirIdx4
 : 
AngledDirIdx18
;

  SearchDirs.insert(SearchDirs.begin() + idx, dir);

  SearchDirsUsage.insert(SearchDirsUsage.begin() + idx, false);

  if (!isAngled)

    AngledDirIdx++;

  SystemDirIdx++;

}

std::vector<bool> HeaderSearch::computeUserEntryUsage() const {

  std::vector<bool> UserEntryUsage(HSOpts->UserEntries.size());

  for (unsigned I = 0, E = SearchDirsUsage.size(); I < E; 
++I15.2k
) {

    // Check whether this DirectoryLookup has been successfully used.

    if (SearchDirsUsage[I]) {

      auto UserEntryIdxIt = SearchDirToHSEntry.find(I);

      // Check whether this DirectoryLookup maps to a HeaderSearch::UserEntry.

      if (UserEntryIdxIt != SearchDirToHSEntry.end())

        UserEntryUsage[UserEntryIdxIt->second] = true;

    }

  }

  return UserEntryUsage;

}

/// CreateHeaderMap - This method returns a HeaderMap for the specified

/// FileEntry, uniquing them through the 'HeaderMaps' datastructure.

const HeaderMap *HeaderSearch::CreateHeaderMap(FileEntryRef FE) {

  // We expect the number of headermaps to be small, and almost always empty.

  // If it ever grows, use of a linear search should be re-evaluated.

  if (!HeaderMaps.empty()) {

    for (unsigned i = 0, e = HeaderMaps.size(); i != e; 
++i11
)

      // Pointer equality comparison of FileEntries works because they are

      // already uniqued by inode.

      if (HeaderMaps[i].first == FE)

        return HeaderMaps[i].second.get();

  }

  if (std::unique_ptr<HeaderMap> HM = HeaderMap::Create(FE, FileMgr)) {

    HeaderMaps.emplace_back(FE, std::move(HM));

    return HeaderMaps.back().second.get();

  }

  return nullptr;

}

/// Get filenames for all registered header maps.

void HeaderSearch::getHeaderMapFileNames(

    SmallVectorImpl<std::string> &Names) const {

  for (auto &HM : HeaderMaps)

    Names.push_back(std::string(HM.first.getName()));

}

std::string HeaderSearch::getCachedModuleFileName(Module *Module) {

  OptionalFileEntryRef ModuleMap =

      getModuleMap().getModuleMapFileForUniquing(Module);

  // The ModuleMap maybe a nullptr, when we load a cached C++ module without

  // *.modulemap file. In this case, just return an empty string.

  if (!ModuleMap)

    return {};

  return getCachedModuleFileName(Module->Name, ModuleMap->getNameAsRequested());

}

std::string HeaderSearch::getPrebuiltModuleFileName(StringRef ModuleName,

                                                    bool FileMapOnly) {

  // First check the module name to pcm file map.

  auto i(HSOpts->PrebuiltModuleFiles.find(ModuleName));

  if (i != HSOpts->PrebuiltModuleFiles.end())

    return i->second;

  if (FileMapOnly || 
HSOpts->PrebuiltModulePaths.empty()335
)

    return {};

  // Then go through each prebuilt module directory and try to find the pcm

  // file.

  for (const std::string &Dir : HSOpts->PrebuiltModulePaths) {

    SmallString<256> Result(Dir);

    llvm::sys::fs::make_absolute(Result);

    if (ModuleName.contains(':'))

      // The separator of C++20 modules partitions (':') is not good for file

      // systems, here clang and gcc choose '-' by default since it is not a

      // valid character of C++ indentifiers. So we could avoid conflicts.

      llvm::sys::path::append(Result, ModuleName.split(':').first + "-" +

                                          ModuleName.split(':').second +

                                          ".pcm");

    else

      llvm::sys::path::append(Result, ModuleName + ".pcm");

    if (getFileMgr().getFile(Result.str()))

      return std::string(Result);

  }

  return {};

}

std::string HeaderSearch::getPrebuiltImplicitModuleFileName(Module *Module) {

  OptionalFileEntryRef ModuleMap =

      getModuleMap().getModuleMapFileForUniquing(Module);

  StringRef ModuleName = Module->Name;

  StringRef ModuleMapPath = ModuleMap->getName();

  StringRef ModuleCacheHash = HSOpts->DisableModuleHash ? 
""0
 : getModuleHash();

  for (const std::string &Dir : HSOpts->PrebuiltModulePaths) {

    SmallString<256> CachePath(Dir);

    llvm::sys::fs::make_absolute(CachePath);

    llvm::sys::path::append(CachePath, ModuleCacheHash);

    std::string FileName =

        getCachedModuleFileNameImpl(ModuleName, ModuleMapPath, CachePath);

    if (!FileName.empty() && getFileMgr().getFile(FileName))

      return FileName;

  }

  return {};

}

std::string HeaderSearch::getCachedModuleFileName(StringRef ModuleName,

                                                  StringRef ModuleMapPath) {

  return getCachedModuleFileNameImpl(ModuleName, ModuleMapPath,

                                     getModuleCachePath());

}

std::string HeaderSearch::getCachedModuleFileNameImpl(StringRef ModuleName,

                                                      StringRef ModuleMapPath,

                                                      StringRef CachePath) {

  // If we don't have a module cache path or aren't supposed to use one, we

  // can't do anything.

  if (CachePath.empty())

    return {};

  SmallString<256> Result(CachePath);

  llvm::sys::fs::make_absolute(Result);

  if (HSOpts->DisableModuleHash) {

    llvm::sys::path::append(Result, ModuleName + ".pcm");

  } else {

    // Construct the name <ModuleName>-<hash of ModuleMapPath>.pcm which should

    // ideally be globally unique to this particular module. Name collisions

    // in the hash are safe (because any translation unit can only import one

    // module with each name), but result in a loss of caching.

    //

    // To avoid false-negatives, we form as canonical a path as we can, and map

    // to lower-case in case we're on a case-insensitive file system.

    SmallString<128> CanonicalPath(ModuleMapPath);

    if (getModuleMap().canonicalizeModuleMapPath(CanonicalPath))

      return {};

    llvm::hash_code Hash = llvm::hash_combine(CanonicalPath.str().lower());

    SmallString<128> HashStr;

    llvm::APInt(64, size_t(Hash)).toStringUnsigned(HashStr, /*Radix*/36);

    llvm::sys::path::append(Result, ModuleName + "-" + HashStr + ".pcm");

  }

  return Result.str().str();

}

Module *HeaderSearch::lookupModule(StringRef ModuleName,

                                   SourceLocation ImportLoc, bool AllowSearch,

                                   bool AllowExtraModuleMapSearch) {

  // Look in the module map to determine if there is a module by this name.

  Module *Module = ModMap.findModule(ModuleName);

  if (Module || 
!AllowSearch4.70k
 || 
!HSOpts->ImplicitModuleMaps4.70k
)

    return Module;

  StringRef SearchName = ModuleName;

  Module = lookupModule(ModuleName, SearchName, ImportLoc,

                        AllowExtraModuleMapSearch);

  // The facility for "private modules" -- adjacent, optional module maps named

  // module.private.modulemap that are supposed to define private submodules --

  // may have different flavors of names: FooPrivate, Foo_Private and Foo.Private.

  //

  // Foo.Private is now deprecated in favor of Foo_Private. Users of FooPrivate

  // should also rename to Foo_Private. Representing private as submodules

  // could force building unwanted dependencies into the parent module and cause

  // dependency cycles.

  if (!Module && 
SearchName.consume_back("_Private")48
)

    Module = lookupModule(ModuleName, SearchName, ImportLoc,

                          AllowExtraModuleMapSearch);

  if (!Module && 
SearchName.consume_back("Private")44
)

    Module = lookupModule(ModuleName, SearchName, ImportLoc,

                          AllowExtraModuleMapSearch);

  return Module;

}

Module *HeaderSearch::lookupModule(StringRef ModuleName, StringRef SearchName,

                                   SourceLocation ImportLoc,

                                   bool AllowExtraModuleMapSearch) {

  Module *Module = nullptr;

  // Look through the various header search paths to load any available module

  // maps, searching for a module map that describes this module.

  for (DirectoryLookup &Dir : search_dir_range()) {

    if (Dir.isFramework()) {

      // Search for or infer a module map for a framework. Here we use

      // SearchName rather than ModuleName, to permit finding private modules

      // named FooPrivate in buggy frameworks named Foo.

      SmallString<128> FrameworkDirName;

      FrameworkDirName += Dir.getFrameworkDirRef()->getName();

      llvm::sys::path::append(FrameworkDirName, SearchName + ".framework");

      if (auto FrameworkDir =

              FileMgr.getOptionalDirectoryRef(FrameworkDirName)) {

        bool IsSystem = Dir.getDirCharacteristic() != SrcMgr::C_User;

        Module = loadFrameworkModule(ModuleName, *FrameworkDir, IsSystem);

        if (Module)

          break;

      }

    }

    // FIXME: Figure out how header maps and module maps will work together.

    // Only deal with normal search directories.

    if (!Dir.isNormalDir())

      continue;

    bool IsSystem = Dir.isSystemHeaderDirectory();

    // Only returns std::nullopt if not a normal directory, which we just

    // checked

    DirectoryEntryRef NormalDir = *Dir.getDirRef();

    // Search for a module map file in this directory.

    if (loadModuleMapFile(NormalDir, IsSystem,

                          /*IsFramework*/false) == LMM_NewlyLoaded) {

      // We just loaded a module map file; check whether the module is

      // available now.

      Module = ModMap.findModule(ModuleName);

      if (Module)

        break;

    }

    // Search for a module map in a subdirectory with the same name as the

    // module.

    SmallString<128> NestedModuleMapDirName;

    NestedModuleMapDirName = Dir.getDirRef()->getName();

    llvm::sys::path::append(NestedModuleMapDirName, ModuleName);

    if (loadModuleMapFile(NestedModuleMapDirName, IsSystem,

                          /*IsFramework*/false) == LMM_NewlyLoaded){

      // If we just loaded a module map file, look for the module again.

      Module = ModMap.findModule(ModuleName);

      if (Module)

        break;

    }

    // If we've already performed the exhaustive search for module maps in this

    // search directory, don't do it again.

    if (Dir.haveSearchedAllModuleMaps())

      continue;

    // Load all module maps in the immediate subdirectories of this search

    // directory if ModuleName was from @import.

    if (AllowExtraModuleMapSearch)

      loadSubdirectoryModuleMaps(Dir);

    // Look again for the module.

    Module = ModMap.findModule(ModuleName);

    if (Module)

      break;

  }

  return Module;

}

void HeaderSearch::indexInitialHeaderMaps() {

  llvm::StringMap<unsigned, llvm::BumpPtrAllocator> Index(SearchDirs.size());

  // Iterate over all filename keys and associate them with the index i.

  for (unsigned i = 0; i != SearchDirs.size(); 
++i37
) {

    auto &Dir = SearchDirs[i];

    // We're concerned with only the initial contiguous run of header

    // maps within SearchDirs, which can be 99% of SearchDirs when

    // SearchDirs.size() is ~10000.

    if (!Dir.isHeaderMap()) {

      SearchDirHeaderMapIndex = std::move(Index);

      FirstNonHeaderMapSearchDirIdx = i;

      break;

    }

    // Give earlier keys precedence over identical later keys.

    
auto Callback = [&](StringRef Filename) 37
{

      Index.try_emplace(Filename.lower(), i);

    };

    Dir.getHeaderMap()->forEachKey(Callback);

  }

}

//===----------------------------------------------------------------------===//

// File lookup within a DirectoryLookup scope

//===----------------------------------------------------------------------===//

/// getName - Return the directory or filename corresponding to this lookup

/// object.

StringRef DirectoryLookup::getName() const {

  if (isNormalDir())

    return getDirRef()->getName();

  if (isFramework())

    return getFrameworkDirRef()->getName();

  assert(isHeaderMap() && "Unknown DirectoryLookup");

  return getHeaderMap()->getFileName();

}

OptionalFileEntryRef HeaderSearch::getFileAndSuggestModule(

    StringRef FileName, SourceLocation IncludeLoc, const DirectoryEntry *Dir,

    bool IsSystemHeaderDir, Module *RequestingModule,

    ModuleMap::KnownHeader *SuggestedModule, bool OpenFile /*=true*/,

    bool CacheFailures /*=true*/) {

  // If we have a module map that might map this header, load it and

  // check whether we'll have a suggestion for a module.

  auto File = getFileMgr().getFileRef(FileName, OpenFile, CacheFailures);

  if (!File) {

    // For rare, surprising errors (e.g. "out of file handles"), diag the EC

    // message.

    std::error_code EC = llvm::errorToErrorCode(File.takeError());

    if (EC != llvm::errc::no_such_file_or_directory &&

        
EC != llvm::errc::invalid_argument13
 &&

        
EC != llvm::errc::is_a_directory13
 && 
EC != llvm::errc::not_a_directory1
) {

      Diags.Report(IncludeLoc, diag::err_cannot_open_file)

          << FileName << EC.message();

    }

    return std::nullopt;

  }

  // If there is a module that corresponds to this header, suggest it.

  if (!findUsableModuleForHeader(

          *File, Dir ? 
Dir3.47M
 : 
File->getFileEntry().getDir()4.36k
, RequestingModule,

          SuggestedModule, IsSystemHeaderDir))

    return std::nullopt;

  return *File;

}

/// LookupFile - Lookup the specified file in this search path, returning it

/// if it exists or returning null if not.

OptionalFileEntryRef DirectoryLookup::LookupFile(

    StringRef &Filename, HeaderSearch &HS, SourceLocation IncludeLoc,

    SmallVectorImpl<char> *SearchPath, SmallVectorImpl<char> *RelativePath,

    Module *RequestingModule, ModuleMap::KnownHeader *SuggestedModule,

    bool &InUserSpecifiedSystemFramework, bool &IsFrameworkFound,

    bool &IsInHeaderMap, SmallVectorImpl<char> &MappedName,

    bool OpenFile) const {

  InUserSpecifiedSystemFramework = false;

  IsInHeaderMap = false;

  MappedName.clear();

  SmallString<1024> TmpDir;

  if (isNormalDir()) {

    // Concatenate the requested file onto the directory.

    TmpDir = getDirRef()->getName();

    llvm::sys::path::append(TmpDir, Filename);

    if (SearchPath) {

      StringRef SearchPathRef(getDirRef()->getName());

      SearchPath->clear();

      SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());

    }

    if (RelativePath) {

      RelativePath->clear();

      RelativePath->append(Filename.begin(), Filename.end());

    }

    return HS.getFileAndSuggestModule(

        TmpDir, IncludeLoc, getDir(), isSystemHeaderDirectory(),

        RequestingModule, SuggestedModule, OpenFile);

  }

  if (isFramework())

    return DoFrameworkLookup(Filename, HS, SearchPath, RelativePath,

                             RequestingModule, SuggestedModule,

                             InUserSpecifiedSystemFramework, IsFrameworkFound);

  assert(isHeaderMap() && "Unknown directory lookup");

  const HeaderMap *HM = getHeaderMap();

  SmallString<1024> Path;

  StringRef Dest = HM->lookupFilename(Filename, Path);

  if (Dest.empty())

    return std::nullopt;

  IsInHeaderMap = true;

  auto FixupSearchPathAndFindUsableModule =

      [&](FileEntryRef File) -> OptionalFileEntryRef {

    if (SearchPath) {

      StringRef SearchPathRef(getName());

      SearchPath->clear();

      SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());

    }

    if (RelativePath) {

      RelativePath->clear();

      RelativePath->append(Filename.begin(), Filename.end());

    }

    if (!HS.findUsableModuleForHeader(File, File.getFileEntry().getDir(),

                                      RequestingModule, SuggestedModule,

                                      isSystemHeaderDirectory())) {

      return std::nullopt;

    }

    return File;

  };

  // Check if the headermap maps the filename to a framework include

  // ("Foo.h" -> "Foo/Foo.h"), in which case continue header lookup using the

  // framework include.

  if (llvm::sys::path::is_relative(Dest)) {

    MappedName.append(Dest.begin(), Dest.end());

    Filename = StringRef(MappedName.begin(), MappedName.size());

    Dest = HM->lookupFilename(Filename, Path);

  }

  if (auto Res = HS.getFileMgr().getOptionalFileRef(Dest, OpenFile)) {

    return FixupSearchPathAndFindUsableModule(*Res);

  }

  // Header maps need to be marked as used whenever the filename matches.

  // The case where the target file **exists** is handled by callee of this

  // function as part of the regular logic that applies to include search paths.

  // The case where the target file **does not exist** is handled here:

  HS.noteLookupUsage(HS.searchDirIdx(*this), IncludeLoc);

  return std::nullopt;

}

/// Given a framework directory, find the top-most framework directory.

///

/// \param FileMgr The file manager to use for directory lookups.

/// \param DirName The name of the framework directory.

/// \param SubmodulePath Will be populated with the submodule path from the

/// returned top-level module to the originally named framework.

static OptionalDirectoryEntryRef

getTopFrameworkDir(FileManager &FileMgr, StringRef DirName,

                   SmallVectorImpl<std::string> &SubmodulePath) {

  assert(llvm::sys::path::extension(DirName) == ".framework" &&

         "Not a framework directory");

  // Note: as an egregious but useful hack we use the real path here, because

  // frameworks moving between top-level frameworks to embedded frameworks tend

  // to be symlinked, and we base the logical structure of modules on the

  // physical layout. In particular, we need to deal with crazy includes like

  //

  //   #include <Foo/Frameworks/Bar.framework/Headers/Wibble.h>

  //

  // where 'Bar' used to be embedded in 'Foo', is now a top-level framework

  // which one should access with, e.g.,

  //

  //   #include <Bar/Wibble.h>

  //

  // Similar issues occur when a top-level framework has moved into an

  // embedded framework.

  auto TopFrameworkDir = FileMgr.getOptionalDirectoryRef(DirName);

  if (TopFrameworkDir)

    DirName = FileMgr.getCanonicalName(*TopFrameworkDir);

  do {

    // Get the parent directory name.

    DirName = llvm::sys::path::parent_path(DirName);

    if (DirName.empty())

      break;

    // Determine whether this directory exists.

    auto Dir = FileMgr.getOptionalDirectoryRef(DirName);

    if (!Dir)

      break;

    // If this is a framework directory, then we're a subframework of this

    // framework.

    if (llvm::sys::path::extension(DirName) == ".framework") {

      SubmodulePath.push_back(std::string(llvm::sys::path::stem(DirName)));

      TopFrameworkDir = *Dir;

    }

  } while (true);

  return TopFrameworkDir;

}

static bool needModuleLookup(Module *RequestingModule,

                             bool HasSuggestedModule) {

  return HasSuggestedModule ||

         
(17.2k
RequestingModule17.2k
 && 
RequestingModule->NoUndeclaredIncludes461
);

}

/// DoFrameworkLookup - Do a lookup of the specified file in the current

/// DirectoryLookup, which is a framework directory.

OptionalFileEntryRef DirectoryLookup::DoFrameworkLookup(

    StringRef Filename, HeaderSearch &HS, SmallVectorImpl<char> *SearchPath,

    SmallVectorImpl<char> *RelativePath, Module *RequestingModule,

    ModuleMap::KnownHeader *SuggestedModule,

    bool &InUserSpecifiedSystemFramework, bool &IsFrameworkFound) const {

  FileManager &FileMgr = HS.getFileMgr();

  // Framework names must have a '/' in the filename.

  size_t SlashPos = Filename.find('/');

  if (SlashPos == StringRef::npos)

    return std::nullopt;

  // Find out if this is the home for the specified framework, by checking

  // HeaderSearch.  Possible answers are yes/no and unknown.

  FrameworkCacheEntry &CacheEntry =

    HS.LookupFrameworkCache(Filename.substr(0, SlashPos));

  // If it is known and in some other directory, fail.

  if (CacheEntry.Directory && 
CacheEntry.Directory != getFrameworkDirRef()337k
)

    return std::nullopt;

  // Otherwise, construct the path to this framework dir.

  // FrameworkName = "/System/Library/Frameworks/"

  SmallString<1024> FrameworkName;

  FrameworkName += getFrameworkDirRef()->getName();

  if (FrameworkName.empty() || FrameworkName.back() != '/')

    FrameworkName.push_back('/');

  // FrameworkName = "/System/Library/Frameworks/Cocoa"

  StringRef ModuleName(Filename.begin(), SlashPos);

  FrameworkName += ModuleName;

  // FrameworkName = "/System/Library/Frameworks/Cocoa.framework/"

  FrameworkName += ".framework/";

  // If the cache entry was unresolved, populate it now.

  if (!CacheEntry.Directory) {

    ++NumFrameworkLookups;

    // If the framework dir doesn't exist, we fail.

    auto Dir = FileMgr.getDirectory(FrameworkName);

    if (!Dir)

      return std::nullopt;

    // Otherwise, if it does, remember that this is the right direntry for this

    // framework.

    CacheEntry.Directory = getFrameworkDirRef();

    // If this is a user search directory, check if the framework has been

    // user-specified as a system framework.

    if (getDirCharacteristic() == SrcMgr::C_User) {

      SmallString<1024> SystemFrameworkMarker(FrameworkName);

      SystemFrameworkMarker += ".system_framework";

      if (llvm::sys::fs::exists(SystemFrameworkMarker)) {

        CacheEntry.IsUserSpecifiedSystemFramework = true;

      }

    }

  }

  // Set out flags.

  InUserSpecifiedSystemFramework = CacheEntry.IsUserSpecifiedSystemFramework;

  IsFrameworkFound = CacheEntry.Directory.has_value();

  if (RelativePath) {

    RelativePath->clear();

    RelativePath->append(Filename.begin()+SlashPos+1, Filename.end());

  }

  // Check "/System/Library/Frameworks/Cocoa.framework/Headers/file.h"

  unsigned OrigSize = FrameworkName.size();

  FrameworkName += "Headers/";

  if (SearchPath) {

    SearchPath->clear();

    // Without trailing '/'.

    SearchPath->append(FrameworkName.begin(), FrameworkName.end()-1);

  }

  FrameworkName.append(Filename.begin()+SlashPos+1, Filename.end());

  auto File =

      FileMgr.getOptionalFileRef(FrameworkName, /*OpenFile=*/!SuggestedModule);

  if (!File) {

    // Check "/System/Library/Frameworks/Cocoa.framework/PrivateHeaders/file.h"

    const char *Private = "Private";

    FrameworkName.insert(FrameworkName.begin()+OrigSize, Private,

                         Private+strlen(Private));

    if (SearchPath)

      SearchPath->insert(SearchPath->begin()+OrigSize, Private,

                         Private+strlen(Private));

    File = FileMgr.getOptionalFileRef(FrameworkName,

                                      /*OpenFile=*/!SuggestedModule);

  }

  // If we found the header and are allowed to suggest a module, do so now.

  if (File && 
needModuleLookup(RequestingModule, SuggestedModule)310k
) {

    // Find the framework in which this header occurs.

    StringRef FrameworkPath = File->getDir().getName();

    bool FoundFramework = false;

    do {

      // Determine whether this directory exists.

      auto Dir = FileMgr.getDirectory(FrameworkPath);

      if (!Dir)

        break;

      // If this is a framework directory, then we're a subframework of this

      // framework.

      if (llvm::sys::path::extension(FrameworkPath) == ".framework") {

        FoundFramework = true;

        break;

      }

      // Get the parent directory name.

      FrameworkPath = llvm::sys::path::parent_path(FrameworkPath);

      if (FrameworkPath.empty())

        break;

    } while (true);

    bool IsSystem = getDirCharacteristic() != SrcMgr::C_User;

    if (FoundFramework) {

      if (!HS.findUsableModuleForFrameworkHeader(*File, FrameworkPath,

                                                 RequestingModule,

                                                 SuggestedModule, IsSystem))

        return std::nullopt;

    } else {

      if (!HS.findUsableModuleForHeader(*File, getDir(), RequestingModule,

                                        SuggestedModule, IsSystem))

        return std::nullopt;

    }

  }

  if (File)

    return *File;

  return std::nullopt;

}

void HeaderSearch::cacheLookupSuccess(LookupFileCacheInfo &CacheLookup,

                                      ConstSearchDirIterator HitIt,

                                      SourceLocation Loc) {

  CacheLookup.HitIt = HitIt;

  noteLookupUsage(HitIt.Idx, Loc);

}

void HeaderSearch::noteLookupUsage(unsigned HitIdx, SourceLocation Loc) {

  SearchDirsUsage[HitIdx] = true;

  auto UserEntryIdxIt = SearchDirToHSEntry.find(HitIdx);

  if (UserEntryIdxIt != SearchDirToHSEntry.end())

    Diags.Report(Loc, diag::remark_pp_search_path_usage)

        << HSOpts->UserEntries[UserEntryIdxIt->second].Path;

}

void HeaderSearch::setTarget(const TargetInfo &Target) {

  ModMap.setTarget(Target);

}

//===----------------------------------------------------------------------===//

// Header File Location.

//===----------------------------------------------------------------------===//

/// Return true with a diagnostic if the file that MSVC would have found

/// fails to match the one that Clang would have found with MSVC header search

/// disabled.

static bool checkMSVCHeaderSearch(DiagnosticsEngine &Diags,

                                  OptionalFileEntryRef MSFE,

                                  const FileEntry *FE,

                                  SourceLocation IncludeLoc) {

  if (MSFE && 
FE != *MSFE3
) {

    Diags.Report(IncludeLoc, diag::ext_pp_include_search_ms) << MSFE->getName();

    return true;

  }

  return false;

}

static const char *copyString(StringRef Str, llvm::BumpPtrAllocator &Alloc) {

  assert(!Str.empty());

  char *CopyStr = Alloc.Allocate<char>(Str.size()+1);

  std::copy(Str.begin(), Str.end(), CopyStr);

  CopyStr[Str.size()] = '\0';

  return CopyStr;

}

static bool isFrameworkStylePath(StringRef Path, bool &IsPrivateHeader,

                                 SmallVectorImpl<char> &FrameworkName,

                                 SmallVectorImpl<char> &IncludeSpelling) {

  using namespace llvm::sys;

  path::const_iterator I = path::begin(Path);

  path::const_iterator E = path::end(Path);

  IsPrivateHeader = false;

  // Detect different types of framework style paths:

  //

  //   ...Foo.framework/{Headers,PrivateHeaders}

  //   ...Foo.framework/Versions/{A,Current}/{Headers,PrivateHeaders}

  //   ...Foo.framework/Frameworks/Nested.framework/{Headers,PrivateHeaders}

  //   ...<other variations with 'Versions' like in the above path>

  //

  // and some other variations among these lines.

  int FoundComp = 0;

  while (I != E) {

    if (*I == "Headers") {

      ++FoundComp;

    } else if (*I == "PrivateHeaders") {

      ++FoundComp;

      IsPrivateHeader = true;

    } else if (I->endswith(".framework")) {

      StringRef Name = I->drop_back(10); // Drop .framework

      // Need to reset the strings and counter to support nested frameworks.

      FrameworkName.clear();

      FrameworkName.append(Name.begin(), Name.end());

      IncludeSpelling.clear();

      IncludeSpelling.append(Name.begin(), Name.end());

      FoundComp = 1;

    } else if (FoundComp >= 2) {

      IncludeSpelling.push_back('/');

      IncludeSpelling.append(I->begin(), I->end());

    }

    ++I;

  }

  return !FrameworkName.empty() && 
FoundComp >= 2699k
;

}

static void

diagnoseFrameworkInclude(DiagnosticsEngine &Diags, SourceLocation IncludeLoc,

                         StringRef Includer, StringRef IncludeFilename,

                         FileEntryRef IncludeFE, bool isAngled = false,

                         bool FoundByHeaderMap = false) {

  bool IsIncluderPrivateHeader = false;

  SmallString<128> FromFramework, ToFramework;

  SmallString<128> FromIncludeSpelling, ToIncludeSpelling;

  if (!isFrameworkStylePath(Includer, IsIncluderPrivateHeader, FromFramework,

                            FromIncludeSpelling))

    return;

  bool IsIncludeePrivateHeader = false;

  bool IsIncludeeInFramework =

      isFrameworkStylePath(IncludeFE.getName(), IsIncludeePrivateHeader,

                           ToFramework, ToIncludeSpelling);

  if (!isAngled && 
!FoundByHeaderMap69
) {

    SmallString<128> NewInclude("<");

    if (IsIncludeeInFramework) {

      NewInclude += ToIncludeSpelling;

      NewInclude += ">";

    } else {

      NewInclude += IncludeFilename;

      NewInclude += ">";

    }

    Diags.Report(IncludeLoc, diag::warn_quoted_include_in_framework_header)

        << IncludeFilename

        << FixItHint::CreateReplacement(IncludeLoc, NewInclude);

  }

  // Headers in Foo.framework/Headers should not include headers

  // from Foo.framework/PrivateHeaders, since this violates public/private

  // API boundaries and can cause modular dependency cycles.

  if (!IsIncluderPrivateHeader && 
IsIncludeeInFramework389k
 &&

      
IsIncludeePrivateHeader310k
 && 
FromFramework == ToFramework8
)

    Diags.Report(IncludeLoc, diag::warn_framework_include_private_from_public)

        << IncludeFilename;

}

/// LookupFile - Given a "foo" or \<foo> reference, look up the indicated file,

/// return null on failure.  isAngled indicates whether the file reference is

/// for system \#include's or not (i.e. using <> instead of ""). Includers, if

/// non-empty, indicates where the \#including file(s) are, in case a relative

/// search is needed. Microsoft mode will pass all \#including files.

OptionalFileEntryRef HeaderSearch::LookupFile(

    StringRef Filename, SourceLocation IncludeLoc, bool isAngled,

    ConstSearchDirIterator FromDir, ConstSearchDirIterator *CurDirArg,

    ArrayRef<std::pair<OptionalFileEntryRef, DirectoryEntryRef>> Includers,

    SmallVectorImpl<char> *SearchPath, SmallVectorImpl<char> *RelativePath,

    Module *RequestingModule, ModuleMap::KnownHeader *SuggestedModule,

    bool *IsMapped, bool *IsFrameworkFound, bool SkipCache,

    bool BuildSystemModule, bool OpenFile, bool CacheFailures) {

  ConstSearchDirIterator CurDirLocal = nullptr;

  ConstSearchDirIterator &CurDir = CurDirArg ? 
*CurDirArg3.83M
 : 
CurDirLocal26
;

  if (IsMapped)

    *IsMapped = false;

  if (IsFrameworkFound)

    *IsFrameworkFound = false;

  if (SuggestedModule)

    *SuggestedModule = ModuleMap::KnownHeader();

  // If 'Filename' is absolute, check to see if it exists and no searching.

  if (llvm::sys::path::is_absolute(Filename)) {

    CurDir = nullptr;

    // If this was an #include_next "/absolute/file", fail.

    if (FromDir)

      return std::nullopt;

    if (SearchPath)

      SearchPath->clear();

    if (RelativePath) {

      RelativePath->clear();

      RelativePath->append(Filename.begin(), Filename.end());

    }

    // Otherwise, just return the file.

    return getFileAndSuggestModule(Filename, IncludeLoc, nullptr,

                                   /*IsSystemHeaderDir*/ false,

                                   RequestingModule, SuggestedModule, OpenFile,

                                   CacheFailures);

  }

  // This is the header that MSVC's header search would have found.

  ModuleMap::KnownHeader MSSuggestedModule;

  OptionalFileEntryRef MSFE;

  // Unless disabled, check to see if the file is in the #includer's

  // directory.  This cannot be based on CurDir, because each includer could be

  // a #include of a subdirectory (#include "foo/bar.h") and a subsequent

  // include of "baz.h" should resolve to "whatever/foo/baz.h".

  // This search is not done for <> headers.

  if (!Includers.empty() && 
!isAngled3.80M
 && 
!NoCurDirSearch84.0k
) {

    SmallString<1024> TmpDir;

    bool First = true;

    for (const auto &IncluderAndDir : Includers) {

      OptionalFileEntryRef Includer = IncluderAndDir.first;

      // Concatenate the requested file onto the directory.

      TmpDir = IncluderAndDir.second.getName();

      llvm::sys::path::append(TmpDir, Filename);

      // FIXME: We don't cache the result of getFileInfo across the call to

      // getFileAndSuggestModule, because it's a reference to an element of

      // a container that could be reallocated across this call.

      //

      // If we have no includer, that means we're processing a #include

      // from a module build. We should treat this as a system header if we're

      // building a [system] module.

      bool IncluderIsSystemHeader =

          Includer ? 
getFileInfo(*Includer).DirInfo != SrcMgr::C_User75.6k
 :

          
BuildSystemModule8.39k
;

      if (OptionalFileEntryRef FE = getFileAndSuggestModule(

              TmpDir, IncludeLoc, IncluderAndDir.second, IncluderIsSystemHeader,

              RequestingModule, SuggestedModule)) {

        if (!Includer) {

          assert(First && "only first includer can have no file");

          return FE;

        }

        // Leave CurDir unset.

        // This file is a system header or C++ unfriendly if the old file is.

        //

        // Note that we only use one of FromHFI/ToHFI at once, due to potential

        // reallocation of the underlying vector potentially making the first

        // reference binding dangling.

        HeaderFileInfo &FromHFI = getFileInfo(*Includer);

        unsigned DirInfo = FromHFI.DirInfo;

        bool IndexHeaderMapHeader = FromHFI.IndexHeaderMapHeader;

        StringRef Framework = FromHFI.Framework;

        HeaderFileInfo &ToHFI = getFileInfo(*FE);

        ToHFI.DirInfo = DirInfo;

        ToHFI.IndexHeaderMapHeader = IndexHeaderMapHeader;

        ToHFI.Framework = Framework;

        if (SearchPath) {

          StringRef SearchPathRef(IncluderAndDir.second.getName());

          SearchPath->clear();

          SearchPath->append(SearchPathRef.begin(), SearchPathRef.end());

        }

        if (RelativePath) {

          RelativePath->clear();

          RelativePath->append(Filename.begin(), Filename.end());

        }

        if (First) {

          diagnoseFrameworkInclude(Diags, IncludeLoc,

                                   IncluderAndDir.second.getName(), Filename,

                                   *FE);

          return FE;

        }

        // Otherwise, we found the path via MSVC header search rules.  If

        // -Wmsvc-include is enabled, we have to keep searching to see if we

        // would've found this header in -I or -isystem directories.

        if (Diags.isIgnored(diag::ext_pp_include_search_ms, IncludeLoc)) {

          return FE;

        } else {

          MSFE = FE;

          if (SuggestedModule) {

            MSSuggestedModule = *SuggestedModule;

            *SuggestedModule = ModuleMap::KnownHeader();

          }

          break;

        }

      }

      First = false;

    }

  }

  CurDir = nullptr;

  // If this is a system #include, ignore the user #include locs.

  ConstSearchDirIterator It =

      isAngled ? 
angled_dir_begin()3.74M
 : 
search_dir_begin()16.8k
;

  // If this is a #include_next request, start searching after the directory the

  // file was found in.

  if (FromDir)

    It = FromDir;

  // Cache all of the lookups performed by this method.  Many headers are

  // multiply included, and the "pragma once" optimization prevents them from

  // being relex/pp'd, but they would still have to search through a

  // (potentially huge) series of SearchDirs to find it.

  LookupFileCacheInfo &CacheLookup = LookupFileCache[Filename];

  ConstSearchDirIterator NextIt = std::next(It);

  if (!SkipCache) {

    if (CacheLookup.StartIt == NextIt &&

        
CacheLookup.RequestingModule == RequestingModule3.00M
) {

      // HIT: Skip querying potentially lots of directories for this lookup.

      if (CacheLookup.HitIt)

        It = CacheLookup.HitIt;

      if (CacheLookup.MappedName) {

        Filename = CacheLookup.MappedName;

        if (IsMapped)

          *IsMapped = true;

      }

    } else {

      // MISS: This is the first query, or the previous query didn't match

      // our search start.  We will fill in our found location below, so prime

      // the start point value.

      CacheLookup.reset(RequestingModule, /*NewStartIt=*/NextIt);

      if (It == search_dir_begin() && 
FirstNonHeaderMapSearchDirIdx > 0759k
) {

        // Handle cold misses of user includes in the presence of many header

        // maps.  We avoid searching perhaps thousands of header maps by

        // jumping directly to the correct one or jumping beyond all of them.

        auto Iter = SearchDirHeaderMapIndex.find(Filename.lower());

        if (Iter == SearchDirHeaderMapIndex.end())

          // Not in index => Skip to first SearchDir after initial header maps

          It = search_dir_nth(FirstNonHeaderMapSearchDirIdx);

        else

          // In index => Start with a specific header map

          It = search_dir_nth(Iter->second);

      }

    }