[clang][lex] Introduce `SearchDirIdx` to usage tracking code

[jansvoboda11]

Summary

This patch introduces new SearchDirIdx type to the internal HeaderSearch code that tracks search path usage. The type replaces the current uses of unsigned to identify DirectoryLookup objects.

In a follow-up patch (D116750), this type will become resilient against insertions "into the middle" of SearchDirs as done by HeaderSearch::AddSearchPath().

[ahoppen]

Definitely a lot nicer 👍

clang/include/clang/Lex/HeaderSearch.h

185

I would have expected these to be methods on HeaderSearch. Is there a particular reason why these are methods on SearchDirIdx?

[jansvoboda11]

clang/include/clang/Lex/HeaderSearch.h

185

No particular reason. I agree this makes more sense on HeaderSearch.

[jansvoboda11]

Move SearchDirIdx::get() to HeaderSearch

clang/include/clang/Lex/HeaderSearch.h

struct FrameworkCacheEntry {
   const DirectoryEntry *Directory;
 
   /// Whether this framework has been "user-specified" to be treated as if it
   /// were a system framework (even if it was found outside a system framework
   /// directory).
   bool IsUserSpecifiedSystemFramework;
 };
 
+/// Index of a search directory.
+class SearchDirIdx {
+  /// The underlying index.
+  size_t Idx;
+
+  friend HeaderSearch;
+
+public:
+  explicit SearchDirIdx(size_t Idx) : Idx(Idx) {}
+
+  bool operator==(const SearchDirIdx &Other) const { return Idx == Other.Idx; }
+
+  llvm::hash_code hash_value() const { return Idx; }
+
+  void increment() { ++Idx; }
+};
+} // namespace clang
+
+namespace llvm {
+template <> struct DenseMapInfo<clang::SearchDirIdx> {
+  static inline clang::SearchDirIdx getEmptyKey() {
+    return clang::SearchDirIdx(-1);
+  }
+  static inline clang::SearchDirIdx getTombstoneKey() {
+    return clang::SearchDirIdx(-2);
+  }
+  static unsigned getHashValue(const clang::SearchDirIdx &Val) {
+    return Val.hash_value();
+  }
+  static bool isEqual(const clang::SearchDirIdx &LHS,
+                      const clang::SearchDirIdx &RHS) {
+    return LHS == RHS;
+  }
+};
+} // namespace llvm
+
+namespace clang {
 namespace detail {
 template <bool Const, typename T>
 using Qualified = std::conditional_t<Const, const T, T>;
 
 /// Forward iterator over the search directories of \c HeaderSearch.
 template <bool IsConst>
 struct SearchDirIteratorImpl
     : llvm::iterator_facade_base<SearchDirIteratorImpl<IsConst>,
struct SearchDirIteratorImpl
   SearchDirIteratorImpl &operator=(const SearchDirIteratorImpl &) = default;
 
   bool operator==(const SearchDirIteratorImpl &RHS) const {
     return HS == RHS.HS && Idx == RHS.Idx;
   }
 
   SearchDirIteratorImpl &operator++() {
     assert(*this && "Invalid iterator.");
-    ++Idx;
+    Idx.increment();
     return *this;
   }
 
   Qualified<IsConst, DirectoryLookup> &operator*() const {
     assert(*this && "Invalid iterator.");
-    return HS->SearchDirs[Idx];
+    return HS->getSearchDirAt(Idx);
   }
 
   /// Creates an invalid iterator.
   SearchDirIteratorImpl(std::nullptr_t) : HS(nullptr), Idx(0) {}
 
   /// Checks whether the iterator is valid.
   explicit operator bool() const { return HS != nullptr; }
 
 private:
   /// The parent \c HeaderSearch. This is \c nullptr for invalid iterator.
   Qualified<IsConst, HeaderSearch> *HS;
 
   /// The index of the current element.
-  size_t Idx;
+  SearchDirIdx Idx;
 
   /// The constructor that creates a valid iterator.
   SearchDirIteratorImpl(Qualified<IsConst, HeaderSearch> &HS, size_t Idx)
       : HS(&HS), Idx(Idx) {}
 
   /// Only HeaderSearch is allowed to instantiate valid iterators.
   friend HeaderSearch;
 
class HeaderSearch {
 
   friend ConstSearchDirIterator;
   friend SearchDirIterator;
 
   /// 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;
+  llvm::DenseMap<SearchDirIdx, unsigned> SearchDirToHSEntry;
 
   DiagnosticsEngine &Diags;
   FileManager &FileMgr;
 
   /// \#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;
+  llvm::DenseSet<SearchDirIdx> UsedSearchDirs;
   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,
                       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);
   }
 
   /// 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.
private:
 
   /// Cache the result of a successful lookup at the given include location
   /// 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);
+  /// search path at index \c HitIdx.
+  void noteLookupUsage(SearchDirIdx HitIdx, SourceLocation IncludeLoc);
+
+  /// Get search directory stored at the given index.
+  const DirectoryLookup &getSearchDirAt(SearchDirIdx Idx) const;
+  /// Get search directory stored at the given index.
+  DirectoryLookup &getSearchDirAt(SearchDirIdx Idx);
 
 public:
   /// Retrieve the module map.
   ModuleMap &getModuleMap() { return ModMap; }
 
   /// Retrieve the module map.
   const ModuleMap &getModuleMap() const { return ModMap; }
 
public:
   ConstSearchDirIterator system_dir_begin() const {
     return {*this, SystemDirIdx};
   }
   ConstSearchDirIterator system_dir_end() const {
     return {*this, SearchDirs.size()};
   }
 
   /// Get the index of the given search directory.
-  unsigned searchDirIdx(const DirectoryLookup &DL) const;
+  SearchDirIdx 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

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);
   AngledDirIdx = angledDirIdx;
   SystemDirIdx = systemDirIdx;
   NoCurDirSearch = noCurDirSearch;
-  SearchDirToHSEntry = std::move(searchDirToHSEntry);
+
+  UsedSearchDirs.clear();
+
+  SearchDirToHSEntry.clear();
+  for (const auto &Entry : searchDirToHSEntry)
+    SearchDirToHSEntry.insert({SearchDirIdx(Entry.first), Entry.second});
+
   //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);
   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);
-      // Check whether this DirectoryLookup maps to a HeaderSearch::UserEntry.
-      if (UserEntryIdxIt != SearchDirToHSEntry.end())
-        UserEntryUsage[UserEntryIdxIt->second] = true;
-    }
-  }
+  for (SearchDirIdx Idx : UsedSearchDirs) {
+    auto UserEntryIdxIt = SearchDirToHSEntry.find(Idx);
   return UserEntryUsage;
 }
 
 /// 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.

 
 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;
+void HeaderSearch::noteLookupUsage(SearchDirIdx HitIdx, SourceLocation Loc) {
+  UsedSearchDirs.insert(HitIdx);
 
   auto UserEntryIdxIt = SearchDirToHSEntry.find(HitIdx);
   if (UserEntryIdxIt != SearchDirToHSEntry.end())
     Diags.Report(Loc, diag::remark_pp_search_path_usage)
         << HSOpts->UserEntries[UserEntryIdxIt->second].Path;
 }
 
+const DirectoryLookup &HeaderSearch::getSearchDirAt(SearchDirIdx Idx) const {
+  return SearchDirs[Idx.Idx];
+}
+
+DirectoryLookup &HeaderSearch::getSearchDirAt(SearchDirIdx Idx) {
+  return SearchDirs[Idx.Idx];
+}
+
 void HeaderSearch::setTarget(const TargetInfo &Target) {
   ModMap.setTarget(Target);
 }
 
 //===----------------------------------------------------------------------===//
 // Header File Location.
 //===----------------------------------------------------------------------===//
 

 size_t HeaderSearch::getTotalMemory() const {
   return SearchDirs.capacity()
     + llvm::capacity_in_bytes(FileInfo)
     + llvm::capacity_in_bytes(HeaderMaps)
     + LookupFileCache.getAllocator().getTotalMemory()
     + FrameworkMap.getAllocator().getTotalMemory();
 }
 
-unsigned HeaderSearch::searchDirIdx(const DirectoryLookup &DL) const {
-  return &DL - &*SearchDirs.begin();
+SearchDirIdx HeaderSearch::searchDirIdx(const DirectoryLookup &DL) const {
+  return SearchDirIdx(&DL - &*SearchDirs.begin());
 }
 
 StringRef HeaderSearch::getUniqueFrameworkName(StringRef Framework) {
   return FrameworkNames.insert(Framework).first->first();
 }
 
 bool HeaderSearch::hasModuleMap(StringRef FileName,
                                 const DirectoryEntry *Root,