[clang][lex] Keep references to `DirectoryLookup` objects up-to-date

The elements of `SearchPath::SearchDirs` are being referenced to by their indices. This proved to be error-prone: `HeaderSearch::SearchDirToHSEntry` was accidentally not being updated in `HeaderSearch::AddSearchPath()`. This patch fixes that by referencing `SearchPath::SearchDirs` elements by their address instead, which is stable thanks to the bump-ptr-allocation strategy.

Reviewed By: ahoppen

Differential Revision: https://reviews.llvm.org/D116750

4 files changed, 152 insertions, 73 deletions

diff --git a/clang/include/clang/Lex/HeaderSearch.h b/clang/include/clang/Lex/HeaderSearch.h
index e056f009eae9..5507401f608a 100644
--- a/clang/include/clang/Lex/HeaderSearch.h
+++ b/clang/include/clang/Lex/HeaderSearch.h
@@ -165,22 +165,23 @@ class HeaderSearch {
   /// Header-search options used to initialize this header search.
   std::shared_ptr<HeaderSearchOptions> HSOpts;
 
-  /// Mapping from SearchDir to HeaderSearchOptions::UserEntries indices.
-  llvm::DenseMap<unsigned, unsigned> SearchDirToHSEntry;
-
   DiagnosticsEngine &Diags;
   FileManager &FileMgr;
 
+  /// The allocator owning search directories.
+  llvm::SpecificBumpPtrAllocator<DirectoryLookup> SearchDirsAlloc;
   /// \#include search path information.  Requests for \#include "x" search the
   /// directory of the \#including file first, then each directory in SearchDirs
   /// consecutively. Requests for <x> search the current dir first, then each
   /// directory in SearchDirs, starting at AngledDirIdx, consecutively.  If
   /// NoCurDirSearch is true, then the check for the file in the current
   /// directory is suppressed.
-  std::vector<DirectoryLookup> SearchDirs;
-  /// Whether the DirectoryLookup at the corresponding index in SearchDirs has
-  /// been successfully used to lookup a file.
-  std::vector<bool> SearchDirsUsage;
+  std::vector<DirectoryLookup *> SearchDirs;
+  /// Set of SearchDirs that have been successfully used to lookup a file.
+  llvm::DenseSet<const DirectoryLookup *> UsedSearchDirs;
+  /// Mapping from SearchDir to HeaderSearchOptions::UserEntries indices.
+  llvm::DenseMap<const DirectoryLookup *, unsigned> SearchDirToHSEntry;
+
   unsigned AngledDirIdx = 0;
   unsigned SystemDirIdx = 0;
   bool NoCurDirSearch = false;
@@ -288,8 +289,7 @@ public:
 
   /// Add an additional system search path.
   void AddSystemSearchPath(const DirectoryLookup &dir) {
-    SearchDirs.push_back(dir);
-    SearchDirsUsage.push_back(false);
+    SearchDirs.push_back(storeSearchDir(dir));
   }
 
   /// Set the list of system header prefixes.
@@ -493,7 +493,11 @@ public:
 
   /// Determine which HeaderSearchOptions::UserEntries have been successfully
   /// used so far and mark their index with 'true' in the resulting bit vector.
+  // TODO: Use llvm::BitVector instead.
   std::vector<bool> computeUserEntryUsage() const;
+  /// Return a bit vector of length \c SearchDirs.size() that indicates for each
+  /// search directory whether it was used.
+  std::vector<bool> getSearchDirUsage() const;
 
   /// This method returns a HeaderMap for the specified
   /// FileEntry, uniquing them through the 'HeaderMaps' datastructure.
@@ -623,6 +627,11 @@ public:
   void loadTopLevelSystemModules();
 
 private:
+  /// Stores the given search directory and returns a stable pointer.
+  DirectoryLookup *storeSearchDir(const DirectoryLookup &Dir) {
+    return new (SearchDirsAlloc.Allocate()) DirectoryLookup(Dir);
+  }
+
   /// Lookup a module with the given module name and search-name.
   ///
   /// \param ModuleName The name of the module we're looking for.
@@ -709,8 +718,9 @@ private:
   void cacheLookupSuccess(LookupFileCacheInfo &CacheLookup, unsigned HitIdx,
                           SourceLocation IncludeLoc);
   /// Note that a lookup at the given include location was successful using the
-  /// search path at index `HitIdx`.
-  void noteLookupUsage(unsigned HitIdx, SourceLocation IncludeLoc);
+  /// given search path.
+  void noteLookupUsage(const DirectoryLookup *SearchDir,
+                       SourceLocation IncludeLoc);
 
 public:
   /// Retrieve the module map.
@@ -733,7 +743,8 @@ public:
                                             bool WantExternal = true) const;
 
   // Used by external tools
-  using search_dir_iterator = std::vector<DirectoryLookup>::const_iterator;
+  using search_dir_iterator =
+      llvm::pointee_iterator<decltype(SearchDirs)::const_iterator>;
 
   search_dir_iterator search_dir_begin() const { return SearchDirs.begin(); }
   search_dir_iterator search_dir_end() const { return SearchDirs.end(); }
@@ -761,9 +772,6 @@ public:
 
   search_dir_iterator system_dir_end() const { return SearchDirs.end(); }
 
-  /// Get the index of the given search directory.
-  Optional<unsigned> searchDirIdx(const DirectoryLookup &DL) const;
-
   /// Retrieve a uniqued framework name.
   StringRef getUniqueFrameworkName(StringRef Framework);
 
diff --git a/clang/lib/Lex/HeaderSearch.cpp b/clang/lib/Lex/HeaderSearch.cpp
index d4de4ed156b6..f58813984596 100644
--- a/clang/lib/Lex/HeaderSearch.cpp
+++ b/clang/lib/Lex/HeaderSearch.cpp
@@ -115,19 +115,24 @@ void HeaderSearch::SetSearchPaths(
     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);
+  SearchDirsAlloc.DestroyAll();
+  SearchDirs.clear();
+  for (const DirectoryLookup &Dir : dirs)
+    SearchDirs.push_back(storeSearchDir(Dir));
+  UsedSearchDirs.clear();
+  SearchDirToHSEntry.clear();
+  for (const auto &Entry : searchDirToHSEntry)
+    SearchDirToHSEntry.insert({SearchDirs[Entry.first], Entry.second});
+
   AngledDirIdx = angledDirIdx;
   SystemDirIdx = systemDirIdx;
   NoCurDirSearch = noCurDirSearch;
-  SearchDirToHSEntry = std::move(searchDirToHSEntry);
   //LookupFileCache.clear();
 }
 
 void HeaderSearch::AddSearchPath(const DirectoryLookup &dir, bool isAngled) {
   unsigned idx = isAngled ? SystemDirIdx : AngledDirIdx;
-  SearchDirs.insert(SearchDirs.begin() + idx, dir);
-  SearchDirsUsage.insert(SearchDirsUsage.begin() + idx, false);
+  SearchDirs.insert(SearchDirs.begin() + idx, storeSearchDir(dir));
   if (!isAngled)
     AngledDirIdx++;
   SystemDirIdx++;
@@ -135,10 +140,9 @@ void HeaderSearch::AddSearchPath(const DirectoryLookup &dir, bool isAngled) {
 
 std::vector<bool> HeaderSearch::computeUserEntryUsage() const {
   std::vector<bool> UserEntryUsage(HSOpts->UserEntries.size());
-  for (unsigned I = 0, E = SearchDirsUsage.size(); I < E; ++I) {
-    // Check whether this DirectoryLookup has been successfully used.
-    if (SearchDirsUsage[I]) {
-      auto UserEntryIdxIt = SearchDirToHSEntry.find(I);
+  for (const DirectoryLookup *SearchDir : UsedSearchDirs) {
+    if (UsedSearchDirs.contains(SearchDir)) {
+      auto UserEntryIdxIt = SearchDirToHSEntry.find(SearchDir);
       // Check whether this DirectoryLookup maps to a HeaderSearch::UserEntry.
       if (UserEntryIdxIt != SearchDirToHSEntry.end())
         UserEntryUsage[UserEntryIdxIt->second] = true;
@@ -147,6 +151,14 @@ std::vector<bool> HeaderSearch::computeUserEntryUsage() const {
   return UserEntryUsage;
 }
 
+std::vector<bool> HeaderSearch::getSearchDirUsage() const {
+  std::vector<bool> SearchDirUsage(SearchDirs.size());
+  for (unsigned I = 0, E = SearchDirs.size(); I < E; ++I)
+    if (UsedSearchDirs.contains(SearchDirs[I]))
+      SearchDirUsage[I] = true;
+  return SearchDirUsage;
+}
+
 /// CreateHeaderMap - This method returns a HeaderMap for the specified
 /// FileEntry, uniquing them through the 'HeaderMaps' datastructure.
 const HeaderMap *HeaderSearch::CreateHeaderMap(const FileEntry *FE) {
@@ -301,21 +313,23 @@ Module *HeaderSearch::lookupModule(StringRef ModuleName, StringRef SearchName,
                                    SourceLocation ImportLoc,
                                    bool AllowExtraModuleMapSearch) {
   Module *Module = nullptr;
-  unsigned Idx;
+  DirectoryLookup *SearchDir = nullptr;
 
   // Look through the various header search paths to load any available module
   // maps, searching for a module map that describes this module.
-  for (Idx = 0; Idx != SearchDirs.size(); ++Idx) {
-    if (SearchDirs[Idx].isFramework()) {
+  for (unsigned Idx = 0; Idx != SearchDirs.size(); ++Idx) {
+    SearchDir = SearchDirs[Idx];
+
+    if (SearchDirs[Idx]->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 += SearchDirs[Idx].getFrameworkDir()->getName();
+      FrameworkDirName += SearchDirs[Idx]->getFrameworkDir()->getName();
       llvm::sys::path::append(FrameworkDirName, SearchName + ".framework");
       if (auto FrameworkDir = FileMgr.getDirectory(FrameworkDirName)) {
         bool IsSystem
-          = SearchDirs[Idx].getDirCharacteristic() != SrcMgr::C_User;
+          = SearchDirs[Idx]->getDirCharacteristic() != SrcMgr::C_User;
         Module = loadFrameworkModule(ModuleName, *FrameworkDir, IsSystem);
         if (Module)
           break;
@@ -325,12 +339,12 @@ Module *HeaderSearch::lookupModule(StringRef ModuleName, StringRef SearchName,
     // FIXME: Figure out how header maps and module maps will work together.
 
     // Only deal with normal search directories.
-    if (!SearchDirs[Idx].isNormalDir())
+    if (!SearchDirs[Idx]->isNormalDir())
       continue;
 
-    bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
+    bool IsSystem = SearchDirs[Idx]->isSystemHeaderDirectory();
     // Search for a module map file in this directory.
-    if (loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
+    if (loadModuleMapFile(SearchDirs[Idx]->getDir(), IsSystem,
                           /*IsFramework*/false) == LMM_NewlyLoaded) {
       // We just loaded a module map file; check whether the module is
       // available now.
@@ -342,7 +356,7 @@ Module *HeaderSearch::lookupModule(StringRef ModuleName, StringRef SearchName,
     // Search for a module map in a subdirectory with the same name as the
     // module.
     SmallString<128> NestedModuleMapDirName;
-    NestedModuleMapDirName = SearchDirs[Idx].getDir()->getName();
+    NestedModuleMapDirName = SearchDirs[Idx]->getDir()->getName();
     llvm::sys::path::append(NestedModuleMapDirName, ModuleName);
     if (loadModuleMapFile(NestedModuleMapDirName, IsSystem,
                           /*IsFramework*/false) == LMM_NewlyLoaded){
@@ -354,13 +368,13 @@ Module *HeaderSearch::lookupModule(StringRef ModuleName, StringRef SearchName,
 
     // If we've already performed the exhaustive search for module maps in this
     // search directory, don't do it again.
-    if (SearchDirs[Idx].haveSearchedAllModuleMaps())
+    if (SearchDirs[Idx]->haveSearchedAllModuleMaps())
       continue;
 
     // Load all module maps in the immediate subdirectories of this search
     // directory if ModuleName was from @import.
     if (AllowExtraModuleMapSearch)
-      loadSubdirectoryModuleMaps(SearchDirs[Idx]);
+      loadSubdirectoryModuleMaps(*SearchDirs[Idx]);
 
     // Look again for the module.
     Module = ModMap.findModule(ModuleName);
@@ -369,7 +383,7 @@ Module *HeaderSearch::lookupModule(StringRef ModuleName, StringRef SearchName,
   }
 
   if (Module)
-    noteLookupUsage(Idx, ImportLoc);
+    noteLookupUsage(SearchDir, ImportLoc);
 
   return Module;
 }
@@ -495,7 +509,7 @@ Optional<FileEntryRef> DirectoryLookup::LookupFile(
   // 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);
+  HS.noteLookupUsage(this, IncludeLoc);
   return None;
 }
 
@@ -703,13 +717,14 @@ Optional<FileEntryRef> DirectoryLookup::DoFrameworkLookup(
 void HeaderSearch::cacheLookupSuccess(LookupFileCacheInfo &CacheLookup,
                                       unsigned HitIdx, SourceLocation Loc) {
   CacheLookup.HitIdx = HitIdx;
-  noteLookupUsage(HitIdx, Loc);
+  noteLookupUsage(SearchDirs[HitIdx], Loc);
 }
 
-void HeaderSearch::noteLookupUsage(unsigned HitIdx, SourceLocation Loc) {
-  SearchDirsUsage[HitIdx] = true;
+void HeaderSearch::noteLookupUsage(const DirectoryLookup *SearchDir,
+                                   SourceLocation Loc) {
+  UsedSearchDirs.insert(SearchDir);
 
-  auto UserEntryIdxIt = SearchDirToHSEntry.find(HitIdx);
+  auto UserEntryIdxIt = SearchDirToHSEntry.find(SearchDir);
   if (UserEntryIdxIt != SearchDirToHSEntry.end())
     Diags.Report(Loc, diag::remark_pp_search_path_usage)
         << HSOpts->UserEntries[UserEntryIdxIt->second].Path;
@@ -963,7 +978,7 @@ Optional<FileEntryRef> HeaderSearch::LookupFile(
   // If this is a #include_next request, start searching after the directory the
   // file was found in.
   if (FromDir)
-    i = FromDir-&SearchDirs[0];
+    i = std::distance(SearchDirs.begin(), llvm::find(SearchDirs, FromDir));
 
   // Cache all of the lookups performed by this method.  Many headers are
   // multiply included, and the "pragma once" optimization prevents them from
@@ -996,7 +1011,7 @@ Optional<FileEntryRef> HeaderSearch::LookupFile(
     bool InUserSpecifiedSystemFramework = false;
     bool IsInHeaderMap = false;
     bool IsFrameworkFoundInDir = false;
-    Optional<FileEntryRef> File = SearchDirs[i].LookupFile(
+    Optional<FileEntryRef> File = SearchDirs[i]->LookupFile(
         Filename, *this, IncludeLoc, SearchPath, RelativePath, RequestingModule,
         SuggestedModule, InUserSpecifiedSystemFramework, IsFrameworkFoundInDir,
         IsInHeaderMap, MappedName);
@@ -1018,7 +1033,7 @@ Optional<FileEntryRef> HeaderSearch::LookupFile(
     if (!File)
       continue;
 
-    CurDir = &SearchDirs[i];
+    CurDir = SearchDirs[i];
 
     // This file is a system header or C++ unfriendly if the dir is.
     HeaderFileInfo &HFI = getFileInfo(&File->getFileEntry());
@@ -1440,13 +1455,6 @@ size_t HeaderSearch::getTotalMemory() const {
     + FrameworkMap.getAllocator().getTotalMemory();
 }
 
-Optional<unsigned> HeaderSearch::searchDirIdx(const DirectoryLookup &DL) const {
-  for (unsigned I = 0; I < SearchDirs.size(); ++I)
-    if (&SearchDirs[I] == &DL)
-      return I;
-  return None;
-}
-
 StringRef HeaderSearch::getUniqueFrameworkName(StringRef Framework) {
   return FrameworkNames.insert(Framework).first->first();
 }
@@ -1774,11 +1782,11 @@ void HeaderSearch::collectAllModules(SmallVectorImpl<Module *> &Modules) {
   if (HSOpts->ImplicitModuleMaps) {
     // Load module maps for each of the header search directories.
     for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
-      bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
-      if (SearchDirs[Idx].isFramework()) {
+      bool IsSystem = SearchDirs[Idx]->isSystemHeaderDirectory();
+      if (SearchDirs[Idx]->isFramework()) {
         std::error_code EC;
         SmallString<128> DirNative;
-        llvm::sys::path::native(SearchDirs[Idx].getFrameworkDir()->getName(),
+        llvm::sys::path::native(SearchDirs[Idx]->getFrameworkDir()->getName(),
                                 DirNative);
 
         // Search each of the ".framework" directories to load them as modules.
@@ -1802,16 +1810,16 @@ void HeaderSearch::collectAllModules(SmallVectorImpl<Module *> &Modules) {
       }
 
       // FIXME: Deal with header maps.
-      if (SearchDirs[Idx].isHeaderMap())
+      if (SearchDirs[Idx]->isHeaderMap())
         continue;
 
       // Try to load a module map file for the search directory.
-      loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
+      loadModuleMapFile(SearchDirs[Idx]->getDir(), IsSystem,
                         /*IsFramework*/ false);
 
       // Try to load module map files for immediate subdirectories of this
       // search directory.
-      loadSubdirectoryModuleMaps(SearchDirs[Idx]);
+      loadSubdirectoryModuleMaps(*SearchDirs[Idx]);
     }
   }
 
@@ -1827,14 +1835,13 @@ void HeaderSearch::loadTopLevelSystemModules() {
   // Load module maps for each of the header search directories.
   for (unsigned Idx = 0, N = SearchDirs.size(); Idx != N; ++Idx) {
     // We only care about normal header directories.
-    if (!SearchDirs[Idx].isNormalDir()) {
+    if (!SearchDirs[Idx]->isNormalDir())
       continue;
-    }
 
     // Try to load a module map file for the search directory.
-    loadModuleMapFile(SearchDirs[Idx].getDir(),
-                      SearchDirs[Idx].isSystemHeaderDirectory(),
-                      SearchDirs[Idx].isFramework());
+    loadModuleMapFile(SearchDirs[Idx]->getDir(),
+                      SearchDirs[Idx]->isSystemHeaderDirectory(),
+                      SearchDirs[Idx]->isFramework());
   }
 }
 
@@ -1932,15 +1939,15 @@ std::string HeaderSearch::suggestPathToFileForDiagnostics(
 
   bool BestPrefixIsFramework = false;
   for (unsigned I = 0; I != SearchDirs.size(); ++I) {
-    if (SearchDirs[I].isNormalDir()) {
-      StringRef Dir = SearchDirs[I].getDir()->getName();
+    if (SearchDirs[I]->isNormalDir()) {
+      StringRef Dir = SearchDirs[I]->getDir()->getName();
       if (CheckDir(Dir)) {
         if (IsSystem)
           *IsSystem = BestPrefixLength ? I >= SystemDirIdx : false;
         BestPrefixIsFramework = false;
       }
-    } else if (SearchDirs[I].isFramework()) {
-      StringRef Dir = SearchDirs[I].getFrameworkDir()->getName();
+    } else if (SearchDirs[I]->isFramework()) {
+      StringRef Dir = SearchDirs[I]->getFrameworkDir()->getName();
       if (CheckDir(Dir)) {
         if (IsSystem)
           *IsSystem = BestPrefixLength ? I >= SystemDirIdx : false;
@@ -1961,11 +1968,11 @@ std::string HeaderSearch::suggestPathToFileForDiagnostics(
   // key from header name is user prefered name for the include file.
   StringRef Filename = File.drop_front(BestPrefixLength);
   for (unsigned I = 0; I != SearchDirs.size(); ++I) {
-    if (!SearchDirs[I].isHeaderMap())
+    if (!SearchDirs[I]->isHeaderMap())
       continue;
 
     StringRef SpelledFilename =
-        SearchDirs[I].getHeaderMap()->reverseLookupFilename(Filename);
+        SearchDirs[I]->getHeaderMap()->reverseLookupFilename(Filename);
     if (!SpelledFilename.empty()) {
       Filename = SpelledFilename;
       BestPrefixIsFramework = false;
diff --git a/clang/unittests/Lex/CMakeLists.txt b/clang/unittests/Lex/CMakeLists.txt
index 97a4e5e44608..3b3e3709ab06 100644
--- a/clang/unittests/Lex/CMakeLists.txt
+++ b/clang/unittests/Lex/CMakeLists.txt
@@ -15,6 +15,7 @@ clang_target_link_libraries(LexTests
   PRIVATE
   clangAST
   clangBasic
+  clangFrontend
   clangLex
   clangParse
   clangSema
diff --git a/clang/unittests/Lex/HeaderSearchTest.cpp b/clang/unittests/Lex/HeaderSearchTest.cpp
index a98f90320be8..b283ff45f2c9 100644
--- a/clang/unittests/Lex/HeaderSearchTest.cpp
+++ b/clang/unittests/Lex/HeaderSearchTest.cpp
@@ -15,6 +15,7 @@
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/Basic/TargetOptions.h"
+#include "clang/Frontend/Utils.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/HeaderSearchOptions.h"
 #include "clang/Serialization/InMemoryModuleCache.h"
@@ -24,6 +25,12 @@
 namespace clang {
 namespace {
 
+static std::shared_ptr<TargetOptions> createTargetOptions() {
+  auto TargetOpts = std::make_shared<TargetOptions>();
+  TargetOpts->Triple = "x86_64-apple-darwin11.1.0";
+  return TargetOpts;
+}
+
 // The test fixture.
 class HeaderSearchTest : public ::testing::Test {
 protected:
@@ -31,12 +38,10 @@ protected:
       : VFS(new llvm::vfs::InMemoryFileSystem), FileMgr(FileMgrOpts, VFS),
         DiagID(new DiagnosticIDs()),
         Diags(DiagID, new DiagnosticOptions, new IgnoringDiagConsumer()),
-        SourceMgr(Diags, FileMgr), TargetOpts(new TargetOptions),
+        SourceMgr(Diags, FileMgr), TargetOpts(createTargetOptions()),
+        Target(TargetInfo::CreateTargetInfo(Diags, TargetOpts)),
         Search(std::make_shared<HeaderSearchOptions>(), SourceMgr, Diags,
-               LangOpts, Target.get()) {
-    TargetOpts->Triple = "x86_64-apple-darwin11.1.0";
-    Target = TargetInfo::CreateTargetInfo(Diags, TargetOpts);
-  }
+               LangOpts, Target.get()) {}
 
   void addSearchDir(llvm::StringRef Dir) {
     VFS->addFile(Dir, 0, llvm::MemoryBuffer::getMemBuffer(""), /*User=*/None,
@@ -56,6 +61,27 @@ protected:
     Search.AddSystemSearchPath(DL);
   }
 
+  void setSearchDirs(llvm::ArrayRef<llvm::StringRef> QuotedDirs,
+                     llvm::ArrayRef<llvm::StringRef> AngledDirs) {
+    auto AddPath = [&](StringRef Dir, bool IsAngled) {
+      VFS->addFile(Dir, 0, llvm::MemoryBuffer::getMemBuffer(""), /*User=*/None,
+                   /*Group=*/None, llvm::sys::fs::file_type::directory_file);
+      auto Group = IsAngled ? frontend::IncludeDirGroup::Angled
+                            : frontend::IncludeDirGroup::Quoted;
+      Search.getHeaderSearchOpts().AddPath(Dir, Group,
+                                           /*IsFramework=*/false,
+                                           /*IgnoreSysRoot=*/true);
+    };
+
+    for (llvm::StringRef Dir : QuotedDirs)
+      AddPath(Dir, /*IsAngled=*/false);
+    for (llvm::StringRef Dir : AngledDirs)
+      AddPath(Dir, /*IsAngled=*/true);
+
+    clang::ApplyHeaderSearchOptions(Search, Search.getHeaderSearchOpts(),
+                                    LangOpts, Target->getTriple());
+  }
+
   void addHeaderMap(llvm::StringRef Filename,
                     std::unique_ptr<llvm::MemoryBuffer> Buf,
                     bool isAngled = false) {
@@ -72,6 +98,17 @@ protected:
     Search.AddSearchPath(DL, isAngled);
   }
 
+  void createModule(StringRef Mod) {
+    std::string ModDir = ("/" + Mod).str();
+    std::string ModHeader = (Mod + ".h").str();
+    VFS->addFile(
+        ModDir + "/module.modulemap", 0,
+        llvm::MemoryBuffer::getMemBufferCopy(
+            ("module " + Mod + " { header \"" + ModHeader + "\" }").str()));
+    VFS->addFile(ModDir + "/" + ModHeader, 0,
+                 llvm::MemoryBuffer::getMemBuffer(""));
+  }
+
   IntrusiveRefCntPtr<llvm::vfs::InMemoryFileSystem> VFS;
   FileSystemOptions FileMgrOpts;
   FileManager FileMgr;
@@ -256,5 +293,31 @@ TEST_F(HeaderSearchTest, HeaderMapFrameworkLookup) {
   EXPECT_EQ(FI->Framework.str(), "Foo");
 }
 
+TEST_F(HeaderSearchTest, SearchPathUsage) {
+  Search.getHeaderSearchOpts().ImplicitModuleMaps = true;
+
+  setSearchDirs(/*QuotedDirs=*/{"/M0"}, /*AngledDirs=*/{"/M2", "/M3"});
+  createModule("M0");
+  createModule("M2");
+  createModule("M3");
+
+  {
+    Module *M2 = Search.lookupModule("M2");
+    EXPECT_NE(M2, nullptr);
+    EXPECT_EQ(Search.getSearchDirUsage(), (std::vector<bool>{0, 1, 0}));
+    EXPECT_EQ(Search.computeUserEntryUsage(), (std::vector<bool>{0, 1, 0}));
+  }
+
+  addSearchDir("/M1");
+  createModule("M1");
+
+  {
+    Module *M1 = Search.lookupModule("M1");
+    EXPECT_NE(M1, nullptr);
+    EXPECT_EQ(Search.getSearchDirUsage(), (std::vector<bool>{0, 1, 1, 0}));
+    EXPECT_EQ(Search.computeUserEntryUsage(), (std::vector<bool>{0, 1, 0}));
+  }
+}
+
 } // namespace
 } // namespace clang