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

[jansvoboda11]

Summary

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.

Depends on D117312 & D117566.

[ahoppen]

Adjusting the indices seem pretty fragile to me. Any reason why you wanted to stick with indices as keys instead of switching to something else like I suggested here?

[jansvoboda11]

In D116750#3227143, @ahoppen wrote:

Adjusting the indices seem pretty fragile to me. Any reason why you wanted to stick with indices as keys instead of switching to something else like I suggested here?

I've implemented your suggestion locally like so:

llvm::SpecificBumpPtrAllocator<DirectoryLookup> SearchDirsAlloc;
std::vector<DirectoryLookup *> SearchDirs;
llvm::DenseMap<const DirectoryLookup *, unsigned> SearchDirToHSEntry;
...

In the end, I decided to stick with just updating the indices to avoid creating unnecessary indirection (and replacing . with -> everywhere).

I don't have any preference though, so if you feel strongly about the fragility, I can use addresses to refer to DirectoryLookup objects instead of indices.

[ahoppen]

I would prefer to use std::shared_ptr<DirectoryLookup> instead of unsigned. IIUC we already basically have a level of indirection because if we want to get the DirectoryLookup, we need to find it by its index in SearchDirs. And updating the indices just seems like a hack to me that can be solved more cleanly.

Wouldn’t we also need to update the indices in SearchDirsUsage and ModuleToSearchDirIdx? Or replace those by std::shared_ptr<DirectoryLookup> as well?

[jansvoboda11]

Yeah, in some cases, we'd be just replacing the index-based indirection with address-based indirection (e.g. when working with SearchDirToHSEntry).

However, most existing HeaderSearch algorithms already work with the index and use that to get the DirectoryLookup from SearchDirs. We'd be adding another level of indirection for them: first they'd need to get DirectoryLookup * from SearchDirs with the index and then dereference the pointer. Maybe that's not very important from performance perspective (especially if we bump-ptr-allocate them), but something to be aware of IMO.

The SearchDirsUsage member is a bit-vector that's being inserted into the same way SearchDirs is, so no need to fiddle with indices there. As for ModuleToSearchDirIdx: yes, we'd need to update indices the same way we do here.

[jansvoboda11]

Use pointers instead of indices to identify DirectoryLookup objects.

[ahoppen]

I like this a lot better. Some comments inline.

clang/include/clang/Lex/HeaderSearch.h

179–184

I haven’t tried it but is there a particular reason why this can’t be a const DirectoryLookup *?

clang/lib/Lex/HeaderSearch.cpp

323

Nitpick: SearchDirs[Idx] can be simplified to SearchDir->isFramework(). Similarly below.

clang/unittests/Lex/HeaderSearchTest.cpp

308

Wouldn’t it be cleaner to just check that UsedSearchDirs only contains a single element and that it’s name is /M2? In that case we could also remove getSearchDirUsage.

[jansvoboda11]

clang/include/clang/Lex/HeaderSearch.h

179–184

While iterating over SearchDirs, the elements can be passed to HeaderSearch::loadSubdirectoryModuleMaps that mutates them.

clang/lib/Lex/HeaderSearch.cpp

323

SearchDir will be removed in the following patch: D113676.

clang/unittests/Lex/HeaderSearchTest.cpp

308

Maybe I'm misunderstanding you, but I don't think so. We'd still need accessor for HeaderSearch::UsedSearchDirs and we don't have the expected DirectoryLookup * lying around, making matching more cumbersome:

const llvm::DenseSet<DirectoryLookup *> &UsedSearchDirs =
    Search.getUsedSearchDirs();
EXPECT_EQ(UsedSearchDirs.size(), 2);
EXPECT_EQ(1, llvm::count_if(UsedSearchDirs, [](const auto *SearchDir) {
            return SearchDir->getName() == "/M1";
          }));
EXPECT_EQ(1, llvm::count_if(UsedSearchDirs, [](const auto *SearchDir) {
            return SearchDir->getName() == "/M2";
          }));

or

llvm::DenseSet<std::string> UsedSearchDirsStr;
for (const auto *SearchDir : Search.getUsedSearchDirs())
  UsedSearchDirsStr.insert(SearchDir->getName());
EXPECT_EQ(UsedSearchDirsStr, (llvm::DenseSet<std::string>{"/M1", "/M2"}));

I think having bit-vector, whose indices correspond to the directory names ("/M{i}"), and using operator== for matching is simpler.

Let me know if you had something else in mind.

[ahoppen]

clang/include/clang/Lex/HeaderSearch.h

179–184

OK. Makes sense. Thanks.

clang/lib/Lex/HeaderSearch.cpp

323

Ah, OK. In that case it makes sense to keep using SearchDirs[Idx].

clang/unittests/Lex/HeaderSearchTest.cpp

308

I just don’t like the bit-vectors and basically thought of the second option you were suggesting, but maybe that’s really just personal taste. If you’d like to keep the bit-vector, could you change the comment of getSearchDirUsage to something like

/// Return a vector of length \c SearchDirs.size() that indicates for each search directory whether it was used.

[jansvoboda11]

Update documentation, inline variables in test

[jansvoboda11]

Thanks for the feedback!

clang/unittests/Lex/HeaderSearchTest.cpp

308

I've updated documentation for HeaderSearch::getSearchDirUsage.

[thakis]

1. which is stable thanks to the bump-ptr-allocation strategy. I don't understand this. In each slab, that's true, but why is it true between objects allocated in different slabs?
2. This increases numbers of TUs compiled for LexTests by over 10%. Is there no way around that Frontend dep?

[jansvoboda11]

In D116750#3234261, @thakis wrote:

1. which is stable thanks to the bump-ptr-allocation strategy. I don't understand this. In each slab, that's true, but why is it true between objects allocated in different slabs?

That's referring to the fact that once we allocate new DirectoryLookup with SpecificBumpPtrAllocator, address of that object won't change (unlike with std::vector). This means that we can take the address and use it without worrying about invalidation.

2. This increases numbers of TUs compiled for LexTests by over 10%. Is there no way around that Frontend dep?

I'll look into moving clang::ApplyHeaderSearchOptions from Frontend into Lex.

[thakis]

That's referring to the fact that once we allocate new DirectoryLookup with SpecificBumpPtrAllocator, address of that object won't change (unlike with std::vector). This means that we can take the address and use it without worrying about invalidation.

Ah, "stable" made me think of iteration order, but that's not what you meant. Makes sense, thanks!

[carlosgalvezp]

Hi @jansvoboda11 !

I believe this commit is the root cause of this issue: https://github.com/llvm/llvm-project/issues/53161

Believe it or not, I was (un)lucky enough to run into it. I have bisected the repo and my tests indicate that this commit is the offender. Do you have any obvious idea what could be the problem?

I'm suspecting this is the offender, since it's related to #include_next which is where I get the error:
https://github.com/llvm/llvm-project/commit/8503c688d555014b88849e933bf096035a351586#diff-fb96fa41fef79b66ab53ac1d845ab467defc41c2639e9b0cd60b471b04f898cdR981
To summarize, clang cannot find /usr/include only if I include exactly 511 directories via -I. If I include 510 or 512, then it works fine. I will test if the same happens with smaller powers of two. I have a test script that I can share if you want to test it yourself.

EDIT: the same happen when including exactly 255 directories. It does not happen for 127 and below. It does happen for 1023 and above.

[jansvoboda11]

In D116750#3240363, @carlosgalvezp wrote:

Hi @jansvoboda11 !

I believe this commit is the root cause of this issue: https://github.com/llvm/llvm-project/issues/53161

Believe it or not, I was (un)lucky enough to run into it. I have bisected the repo and my tests indicate that this commit is the offender. Do you have any obvious idea what could be the problem?

I'm suspecting this is the offender, since it's related to #include_next which is where I get the error:
https://github.com/llvm/llvm-project/commit/8503c688d555014b88849e933bf096035a351586#diff-fb96fa41fef79b66ab53ac1d845ab467defc41c2639e9b0cd60b471b04f898cdR981
To summarize, clang cannot find /usr/include only if I include exactly 511 directories via -I. If I include 510 or 512, then it works fine. I will test if the same happens with smaller powers of two. I have a test script that I can share if you want to test it yourself.

EDIT: the same happen when including exactly 255 directories. It does not happen for 127 and below. It does happen for 1023 and above.

Hi, thanks for reporting this. The reproducer script would be helpful. Looking at the code, I don't see anything obviously wrong.

[carlosgalvezp]

In D116750#3240680, @jansvoboda11 wrote:

In D116750#3240363, @carlosgalvezp wrote:

Hi @jansvoboda11 !

I believe this commit is the root cause of this issue: https://github.com/llvm/llvm-project/issues/53161

Believe it or not, I was (un)lucky enough to run into it. I have bisected the repo and my tests indicate that this commit is the offender. Do you have any obvious idea what could be the problem?

I'm suspecting this is the offender, since it's related to #include_next which is where I get the error:
https://github.com/llvm/llvm-project/commit/8503c688d555014b88849e933bf096035a351586#diff-fb96fa41fef79b66ab53ac1d845ab467defc41c2639e9b0cd60b471b04f898cdR981
To summarize, clang cannot find /usr/include only if I include exactly 511 directories via -I. If I include 510 or 512, then it works fine. I will test if the same happens with smaller powers of two. I have a test script that I can share if you want to test it yourself.

EDIT: the same happen when including exactly 255 directories. It does not happen for 127 and below. It does happen for 1023 and above.

Hi, thanks for reporting this. The reproducer script would be helpful. Looking at the code, I don't see anything obviously wrong.

Sure, I attach it do this message. It assumes you run from a place from which you can run ./build/bin/clang.

test.py1 KBDownload

Let me know if I can provide anything else to help! It might not be this commit in particular, perhaps the problem is in some allocator class merged earlier.

[jansvoboda11]

Thank you!

I'm pretty sure it's this commit that causes the failure.

I now see that HeaderSearch::LookupFile callers perform pointer arithmetics on the out-parameter const DirectoryLookup *&CurDir. They rely on the fact that all DirectoryLookup instances are in contiguous memory. That was true when they were stored in std::vector<DirectoryLookup>, but since they are allocated in llvm::SpecificBumpPtrAllocator<DirectoryLookup> after this patch, that assumption is no longer true.

I have reverted the patch for now and will look into fixing this.

[carlosgalvezp]

Great catch and thanks for the revert!

[jansvoboda11]

I'll need to figure out how to efficiently replace the pointer arithmetic performed by Preprocessor::LookupFile, or go back to my first solution: keeping std::vector<DirectoryLookup> and updating indices in AddSearchPath...

[jansvoboda11]

Replace external uses of const DirectoryLookup * by an optional iterator. That's how they get treated by callers.

[jansvoboda11]

clang/include/clang/Lex/HeaderSearch.h

405

This is the interesting change in the latest revision. Callers of this function performed pointer arithmetics on const DirectoryLookup *, essentially treating it as an iterator. Since DirectoryLookup objects are no longer stored in contiguous memory, that's unsafe. I'm using an iterator to allow doing that safely and using llvm::Optional to provide the nullability clients take advantage of.

I don't love the long name that causes a bunch of formatting changes. Maybe it's worth extracting it out of HeaderSearch and giving it shorter name. I also don't love that the API is not the same as for const DirectoryLookup *, leading to some "unnecessary" changes (e.g. CurDir = nullptr -> CurDir.reset()). I think it might be worth creating custom iterator type that would have the original API, but would behave correctly with the new memory setup.

[jansvoboda11]

Rebase on top of D117566.

[jansvoboda11]

clang/include/clang/Lex/HeaderSearch.h

405

Resolved in the latest revision by introducing D117566.

clang/include/clang/Lex/HeaderSearch.h

 /// Encapsulates the information needed to find the file referenced
 /// by a \#include or \#include_next, (sub-)framework lookup, etc.
 class HeaderSearch {
   friend class DirectoryLookup;
 
   /// 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;
 
   /// \#include prefixes for which the 'system header' property is
   /// overridden.
   ///
   /// For a \#include "x" or \#include \<x> directive, the last string in this
void SetSearchPaths(std::vector<DirectoryLookup> dirs, unsigned angledDirIdx,
                       unsigned systemDirIdx, bool noCurDirSearch,
                       llvm::DenseMap<unsigned, unsigned> searchDirToHSEntry);
 
   /// Add an additional search path.
   void AddSearchPath(const DirectoryLookup &dir, bool isAngled);
 
   /// 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.
   void SetSystemHeaderPrefixes(ArrayRef<std::pair<std::string, bool>> P) {
     SystemHeaderPrefixes.assign(P.begin(), P.end());
   }
 
   /// Checks whether the map exists or not.
public:
   /// true.
   ///
   /// \param IsFrameworkFound If non-null, will be set to true if a framework is
   /// found in any of searched SearchDirs. Will be set to false if a framework
   /// is found only through header maps. Doesn't guarantee the requested file is
   /// found.
   Optional<FileEntryRef> LookupFile(
       StringRef Filename, SourceLocation IncludeLoc, bool isAngled,
       const DirectoryLookup *FromDir, const DirectoryLookup *&CurDir,
       ArrayRef<std::pair<const FileEntry *, const DirectoryEntry *>> Includers,
       SmallVectorImpl<char> *SearchPath, SmallVectorImpl<char> *RelativePath,
       Module *RequestingModule, ModuleMap::KnownHeader *SuggestedModule,
       bool *IsMapped, bool *IsFrameworkFound, bool SkipCache = false,
       bool BuildSystemModule = false);
 
   /// Look up a subframework for the specified \#include file.
   ///
public:
   /// Determine whether the given file is known to have ever been \#imported.
   bool hasFileBeenImported(const FileEntry *File) {
     const HeaderFileInfo *FI = getExistingFileInfo(File);
     return FI && FI->isImport;
   }
 
   /// 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.
   const HeaderMap *CreateHeaderMap(const FileEntry *FE);
 
   /// Get filenames for all registered header maps.
   void getHeaderMapFileNames(SmallVectorImpl<std::string> &Names) const;
 
public:
   ///
   /// \param Modules Will be filled with the set of known, top-level modules.
   void collectAllModules(SmallVectorImpl<Module *> &Modules);
 
   /// Load all known, top-level system modules.
   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.
   ///
   /// \param SearchName The "search-name" to derive filesystem paths from
   /// when looking for the module map; this is usually equal to ModuleName,
   /// but for compatibility with some buggy frameworks, additional attempts
   /// may be made to find the module under a related-but-different search-name.
getFileAndSuggestModule(StringRef FileName, SourceLocation IncludeLoc,
                           Module *RequestingModule,
                           ModuleMap::KnownHeader *SuggestedModule);
 
   /// Cache the result of a successful lookup at the given include location
   /// using the search path at index `HitIdx`.
   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.
   ModuleMap &getModuleMap() { return ModMap; }
 
   /// Retrieve the module map.
   const ModuleMap &getModuleMap() const { return ModMap; }
 
   unsigned header_file_size() const { return FileInfo.size(); }
 
   /// Return the HeaderFileInfo structure for the specified FileEntry,
   /// in preparation for updating it in some way.
   HeaderFileInfo &getFileInfo(const FileEntry *FE);
 
   /// Return the HeaderFileInfo structure for the specified FileEntry,
   /// if it has ever been filled in.
   /// \param WantExternal Whether the caller wants purely-external header file
   ///        info (where \p External is true).
   const HeaderFileInfo *getExistingFileInfo(const FileEntry *FE,
                                             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(); }
   unsigned search_dir_size() const { return SearchDirs.size(); }
 
   search_dir_iterator quoted_dir_begin() const {
     return SearchDirs.begin();
   }
public:
   }
 
   search_dir_iterator system_dir_begin() const {
     return SearchDirs.begin() + SystemDirIdx;
   }
 
   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);
 
   /// Suggest a path by which the specified file could be found, for use in
   /// diagnostics to suggest a #include. Returned path will only contain forward
   /// slashes as separators. MainFile is the absolute path of the file that we
   /// are generating the diagnostics for. It will try to shorten the path using
   /// MainFile location, if none of the include search directories were prefix

clang/lib/Lex/HeaderSearch.cpp

 }
 
 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);
+  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++;
 }
 
 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;
     }
   }
   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) {
   // 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; ++i)
       // Pointer equality comparison of FileEntries works because they are
Module = lookupModule(ModuleName, SearchName, ImportLoc,
                           AllowExtraModuleMapSearch);
   return Module;
 }
 
 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;
       }
     }
 
     // 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.
       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 = SearchDirs[Idx].getDir()->getName();
+    NestedModuleMapDirName = SearchDirs[Idx]->getDir()->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 (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);
     if (Module)
       break;
   }
 
   if (Module)
-    noteLookupUsage(Idx, ImportLoc);
+    noteLookupUsage(SearchDir, ImportLoc);
 
   return Module;
 }
 
 //===----------------------------------------------------------------------===//
 // File lookup within a DirectoryLookup scope
 //===----------------------------------------------------------------------===//
 
if (auto Res = HS.getFileMgr().getOptionalFileRef(Dest)) {
     FixupSearchPath();
     return *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);
+  HS.noteLookupUsage(this, IncludeLoc);
   return None;
 }
 
 /// 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
Optional<FileEntryRef> DirectoryLookup::DoFrameworkLookup(
   if (File)
     return *File;
   return None;
 }
 
 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;
 }
 
 void HeaderSearch::setTarget(const TargetInfo &Target) {
   ModMap.setTarget(Target);
 }
Optional<FileEntryRef> HeaderSearch::LookupFile(
   CurDir = nullptr;
 
   // If this is a system #include, ignore the user #include locs.
   unsigned i = isAngled ? AngledDirIdx : 0;
 
   // 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
   // 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];
 
   // If the entry has been previously looked up, the first value will be
Optional<FileEntryRef> HeaderSearch::LookupFile(
 
   SmallString<64> MappedName;
 
   // Check each directory in sequence to see if it contains this file.
   for (; i != SearchDirs.size(); ++i) {
     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);
     if (!MappedName.empty()) {
       assert(IsInHeaderMap && "MappedName should come from a header map");
       CacheLookup.MappedName =
           copyString(MappedName, LookupFileCache.getAllocator());
     }
     if (IsMapped)
       // A filename is mapped when a header map remapped it to a relative path
       // used in subsequent header search or to an absolute path pointing to an
       // existing file.
       *IsMapped |= (!MappedName.empty() || (IsInHeaderMap && File));
     if (IsFrameworkFound)
       // Because we keep a filename remapped for subsequent search directory
       // lookups, ignore IsFrameworkFoundInDir after the first remapping and not
       // just for remapping in a current search directory.
       *IsFrameworkFound |= (IsFrameworkFoundInDir && !CacheLookup.MappedName);
     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());
     HFI.DirInfo = CurDir->getDirCharacteristic();
 
     // If the directory characteristic is User but this framework was
     // user-specified to be treated as a system framework, promote the
     // characteristic.

 size_t HeaderSearch::getTotalMemory() const {
   return SearchDirs.capacity()
     + llvm::capacity_in_bytes(FileInfo)
     + llvm::capacity_in_bytes(HeaderMaps)
     + LookupFileCache.getAllocator().getTotalMemory()
     + 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();
 }
 
 bool HeaderSearch::hasModuleMap(StringRef FileName,
                                 const DirectoryEntry *Root,
                                 bool IsSystem) {
   if (!HSOpts->ImplicitModuleMaps)

 }
 
 void HeaderSearch::collectAllModules(SmallVectorImpl<Module *> &Modules) {
   Modules.clear();
 
   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.
         llvm::vfs::FileSystem &FS = FileMgr.getVirtualFileSystem();
         for (llvm::vfs::directory_iterator Dir = FS.dir_begin(DirNative, EC),
                                            DirEnd;
              Dir != DirEnd && !EC; Dir.increment(EC)) {
           if (llvm::sys::path::extension(Dir->path()) != ".framework")
             continue;
 
           auto FrameworkDir =
               FileMgr.getDirectory(Dir->path());
           if (!FrameworkDir)
             continue;
 
           // Load this framework module.
           loadFrameworkModule(llvm::sys::path::stem(Dir->path()), *FrameworkDir,
                               IsSystem);
         }
         continue;
       }
 
       // 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]);
     }
   }
 
   // Populate the list of modules.
   llvm::transform(ModMap.modules(), std::back_inserter(Modules),
                   [](const auto &NameAndMod) { return NameAndMod.second; });
 }
 
 void HeaderSearch::loadTopLevelSystemModules() {
   if (!HSOpts->ImplicitModuleMaps)
     return;
 
   // 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());
   }
 }
 
 void HeaderSearch::loadSubdirectoryModuleMaps(DirectoryLookup &SearchDir) {
   assert(HSOpts->ImplicitModuleMaps &&
          "Should not be loading subdirectory module maps");
 
   if (SearchDir.haveSearchedAllModuleMaps())
for (auto NI = path::begin(File), NE = path::end(File),
       if (*NI != *DI)
         break;
     }
     return false;
   };
 
   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;
         BestPrefixIsFramework = true;
       }
     }
   }
 
   // Try to shorten include path using TUs directory, if we couldn't find any
   // suitable prefix in include search paths.
   if (!BestPrefixLength && CheckDir(path::parent_path(MainFile))) {
     if (IsSystem)
       *IsSystem = false;
     BestPrefixIsFramework = false;
   }
 
   // Try resolving resulting filename via reverse search in header maps,
   // 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;
       break;
     }
   }
 
   // If the best prefix is a framework path, we need to compute the proper

clang/unittests/Lex/CMakeLists.txt

add_clang_unittest(LexTests
   PPCallbacksTest.cpp
   PPConditionalDirectiveRecordTest.cpp
   )
 
 clang_target_link_libraries(LexTests
   PRIVATE
   clangAST
   clangBasic
+  clangFrontend
   clangLex
   clangParse
   clangSema
   )

clang/unittests/Lex/HeaderSearchTest.cpp

 #include "HeaderMapTestUtils.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/LangOptions.h"
 #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"
 #include "llvm/Support/MemoryBuffer.h"
 #include "gtest/gtest.h"
 
 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:
   HeaderSearchTest()
       : 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,
                  /*Group=*/None, llvm::sys::fs::file_type::directory_file);
     auto DE = FileMgr.getOptionalDirectoryRef(Dir);
     assert(DE);
     auto DL = DirectoryLookup(*DE, SrcMgr::C_User, /*isFramework=*/false);
     Search.AddSearchPath(DL, /*isAngled=*/false);
   }
 
   void addSystemFrameworkSearchDir(llvm::StringRef Dir) {
     VFS->addFile(Dir, 0, llvm::MemoryBuffer::getMemBuffer(""), /*User=*/None,
                  /*Group=*/None, llvm::sys::fs::file_type::directory_file);
     auto DE = FileMgr.getOptionalDirectoryRef(Dir);
     assert(DE);
     auto DL = DirectoryLookup(*DE, SrcMgr::C_System, /*isFramework=*/true);
     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) {
     VFS->addFile(Filename, 0, std::move(Buf), /*User=*/None, /*Group=*/None,
                  llvm::sys::fs::file_type::regular_file);
     auto FE = FileMgr.getFile(Filename, true);
     assert(FE);
 
     // Test class supports only one HMap at a time.
     assert(!HMap);
     HMap = HeaderMap::Create(*FE, FileMgr);
     auto DL =
         DirectoryLookup(HMap.get(), SrcMgr::C_User, /*isFramework=*/false);
     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;
   IntrusiveRefCntPtr<DiagnosticIDs> DiagID;
   DiagnosticsEngine Diags;
   SourceManager SourceMgr;
   LangOptions LangOpts;
   std::shared_ptr<TargetOptions> TargetOpts;
TEST_F(HeaderSearchTest, HeaderMapFrameworkLookup) {
   EXPECT_TRUE(IsMapped);
   auto &FE = FoundFile.getValue();
   auto FI = Search.getExistingFileInfo(FE);
   EXPECT_TRUE(FI);
   EXPECT_TRUE(FI->IsValid);
   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