[clang][lex] Use `ConstSearchDirIterator` in lookup cache

[jansvoboda11]

Summary

This patch starts using the new iterator type in LookupFileCacheInfo.

Depends on D117566.

[ahoppen]

clang/lib/Lex/HeaderSearch.cpp

710

I haven’t looked into this in total details but &* looks a little awkward to me. Dereference a pointer/iteration and then get its pointer value back?

Wouldn’t this hit the same issue that we saw before if serach_dir_begin is allocated in a different bump allocator begin than HitIt?

If possible, would std::distance communicate the intent more clearly?

982

What’s the reason that this can’t be? The current lambda-based implementation looks a little over-complicated to me. But maybe I’m missing something.

ConstSearchDirIterator NextIt = ItCopy;
++NextIt;

or even something equivalent to

ConstSearchDirIterator NextIt = std::next(ItCopy);

[jansvoboda11]

clang/lib/Lex/HeaderSearch.cpp

710

This should really call to searchDirIdx(). That will be updated when we switch to different storage type in a follow up commit.

Since we're using forward iterators, calling std::distance would be O(n) instead of the current O(1).

982

It can be both. I didn't like the former for its verbosity, but std::next should do the trick, thanks!

[jansvoboda11]

Use std::next and ConstSearchDirIterator::Idx.

[jansvoboda11]

clang/lib/Lex/HeaderSearch.cpp

710

(Used ConstSearchDirIterator::Idx for now, but will refactor this with the new storage layout in a follow-up.)

[sberg]

I started to experience Clang crashing when building Firebird (as part of building LibreOffice) in clang-cl mode on Windows, and I think it is due to this change in combination with D2733 by @rnk:

When HeaderSearch::LookupFile exits through one of the if (checkMSVCHeaderSearch... branches introduced in D2733, it does not update CacheLookup.HitIt (through one of the calls to cacheLookupSuccess or via the "Otherwise, didn't find it" step at the end of the function), even though it already may have done the "We will fill in our found location below, so prime the start point value" step of calling CacheLookup.reset. That means that a later call to HeaderSearch::LookupFile can go into the if (!SkipCache && CacheLookup.StartIt == NextIt) true branch, set It = CacheLookup.HitIt to an invalid iterator (the default HitIt = nullptr value), and then assert/crash when dereferencing that invalid It.

Which was not an issue before this change, as the initial HitIdx = 0 was not an invalid value, so i = CacheLookup.HitIdx never caused i to become invalid.

I locally worked around this in my build with

-  if (!SkipCache && CacheLookup.StartIt == NextIt) {
+  if (!SkipCache && CacheLookup.StartIt == NextIt && CacheLookup.HitIt) {

which seems to work well, but I'm not sure what the best real fix would be. (D2733 stated "I believe the correct behavior here is to avoid updating the cache when we find the header via MSVC's search rules.")

[jansvoboda11]

Thanks for reporting this (also reported here: https://github.com/llvm/llvm-project/issues/54426). I have a fix up for review here: D122237.

clang/include/clang/Lex/HeaderSearch.h

class HeaderSearch {
   std::string ModuleCachePath;
 
   /// All of the preprocessor-specific data about files that are
   /// included, indexed by the FileEntry's UID.
   mutable std::vector<HeaderFileInfo> FileInfo;
 
   /// Keeps track of each lookup performed by LookupFile.
   struct LookupFileCacheInfo {
-    /// Starting index in SearchDirs that the cached search was performed from.
-    /// If there is a hit and this value doesn't match the current query, the
-    /// cache has to be ignored.
-    unsigned StartIdx = 0;
+    /// Starting search directory iterator that the cached search was performed
+    /// from. If there is a hit and this value doesn't match the current query,
+    /// the cache has to be ignored.
+    ConstSearchDirIterator StartIt = 0;
 
-    /// The entry in SearchDirs that satisfied the query.
-    unsigned HitIdx = 0;
+    /// The search directory iterator that satisfied the query.
+    ConstSearchDirIterator HitIt = 0;
 
     /// This is non-null if the original filename was mapped to a framework
     /// include via a headermap.
     const char *MappedName = nullptr;
 
     /// Default constructor -- Initialize all members with zero.
     LookupFileCacheInfo() = default;
 
-    void reset(unsigned StartIdx) {
-      this->StartIdx = StartIdx;
-      this->MappedName = nullptr;
+    void reset(ConstSearchDirIterator NewStartIt) {
+      StartIt = NewStartIt;
+      MappedName = nullptr;
     }
   };
   llvm::StringMap<LookupFileCacheInfo, llvm::BumpPtrAllocator> LookupFileCache;
 
   /// Collection mapping a framework or subframework
   /// name like "Carbon" to the Carbon.framework directory.
   llvm::StringMap<FrameworkCacheEntry, llvm::BumpPtrAllocator> FrameworkMap;
 
private:
   /// module.
   Optional<FileEntryRef>
   getFileAndSuggestModule(StringRef FileName, SourceLocation IncludeLoc,
                           const DirectoryEntry *Dir, bool IsSystemHeaderDir,
                           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,
+  /// using the search path at \c HitIt.
+  void cacheLookupSuccess(LookupFileCacheInfo &CacheLookup,
+                          ConstSearchDirIterator HitIt,
                           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);
 
 public:
   /// Retrieve the module map.
   ModuleMap &getModuleMap() { return ModMap; }
 

clang/lib/Lex/HeaderSearch.cpp

if (File && needModuleLookup(RequestingModule, SuggestedModule)) {
     }
   }
   if (File)
     return *File;
   return None;
 }
 
 void HeaderSearch::cacheLookupSuccess(LookupFileCacheInfo &CacheLookup,
-                                      unsigned HitIdx, SourceLocation Loc) {
-  CacheLookup.HitIdx = HitIdx;
-  noteLookupUsage(HitIdx, Loc);
+                                      ConstSearchDirIterator HitIt,
+                                      SourceLocation Loc) {
+  CacheLookup.HitIt = HitIt;
+  noteLookupUsage(&*HitIt - &*search_dir_begin(), 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)
for (const auto &IncluderAndDir : Includers) {
       }
       First = false;
     }
   }
 
   CurDir = nullptr;
 
   // If this is a system #include, ignore the user #include locs.
-  unsigned i = isAngled ? AngledDirIdx : 0;
+  ConstSearchDirIterator It =
+      isAngled ? angled_dir_begin() : search_dir_begin();
 
   // If this is a #include_next request, start searching after the directory the
   // file was found in.
   if (FromDir)
-    i = FromDir.Idx;
+    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 = [](auto ItCopy) { return ++ItCopy; }(It);
+
   // If the entry has been previously looked up, the first value will be
   // non-zero.  If the value is equal to i (the start point of our search), then
   // this is a matching hit.
-  if (!SkipCache && CacheLookup.StartIdx == i+1) {
+  if (!SkipCache && CacheLookup.StartIt == NextIt) {
     // Skip querying potentially lots of directories for this lookup.
-    i = CacheLookup.HitIdx;
+    It = CacheLookup.HitIt;
     if (CacheLookup.MappedName) {
       Filename = CacheLookup.MappedName;
       if (IsMapped)
         *IsMapped = true;
     }
   } else {
     // Otherwise, 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(/*StartIdx=*/i+1);
+    CacheLookup.reset(/*NewStartIt=*/NextIt);
   }
 
   SmallString<64> MappedName;
 
   // Check each directory in sequence to see if it contains this file.
-  for (; i != SearchDirs.size(); ++i) {
+  for (; It != search_dir_end(); ++It) {
     bool InUserSpecifiedSystemFramework = false;
     bool IsInHeaderMap = false;
     bool IsFrameworkFoundInDir = false;
-    Optional<FileEntryRef> File = SearchDirs[i].LookupFile(
+    Optional<FileEntryRef> File = It->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 = ConstSearchDirIterator(*this, i);
+    CurDir = It;
 
     // 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.
for (; It != search_dir_end(); ++It) {
 
     bool FoundByHeaderMap = !IsMapped ? false : *IsMapped;
     if (!Includers.empty())
       diagnoseFrameworkInclude(
           Diags, IncludeLoc, Includers.front().second->getName(), Filename,
           &File->getFileEntry(), isAngled, FoundByHeaderMap);
 
     // Remember this location for the next lookup we do.
-    cacheLookupSuccess(CacheLookup, i, IncludeLoc);
+    cacheLookupSuccess(CacheLookup, It, IncludeLoc);
     return File;
   }
 
   // If we are including a file with a quoted include "foo.h" from inside
   // a header in a framework that is currently being built, and we couldn't
   // resolve "foo.h" any other way, change the include to <Foo/foo.h>, where
   // "Foo" is the name of the framework in which the including header was found.
   if (!Includers.empty() && Includers.front().first && !isAngled &&
if (IncludingHFI.IndexHeaderMapHeader) {
                                 File ? &File->getFileEntry() : nullptr,
                                 IncludeLoc)) {
         if (SuggestedModule)
           *SuggestedModule = MSSuggestedModule;
         return MSFE;
       }
 
       cacheLookupSuccess(LookupFileCache[Filename],
-                         LookupFileCache[ScratchFilename].HitIdx, IncludeLoc);
+                         LookupFileCache[ScratchFilename].HitIt, IncludeLoc);
       // FIXME: SuggestedModule.
       return File;
     }
   }
 
   if (checkMSVCHeaderSearch(Diags, MSFE ? &MSFE->getFileEntry() : nullptr,
                             nullptr, IncludeLoc)) {
     if (SuggestedModule)
       *SuggestedModule = MSSuggestedModule;
     return MSFE;
   }
 
   // Otherwise, didn't find it. Remember we didn't find this.
-  CacheLookup.HitIdx = SearchDirs.size();
+  CacheLookup.HitIt = search_dir_end();
   return None;
 }
 
 /// LookupSubframeworkHeader - Look up a subframework for the specified
 /// \#include file.  For example, if \#include'ing <HIToolbox/HIToolbox.h> from
 /// within ".../Carbon.framework/Headers/Carbon.h", check to see if HIToolbox
 /// is a subframework within Carbon.framework.  If so, return the FileEntry
 /// for the designated file, otherwise return null.