[clang][lex] Use `SearchDirIterator` types in for loops

[jansvoboda11]

Summary

This patch replaces a lot of index-based loops with iterators and ranges.

Depends on D117566.

[ahoppen]

Nice. I think this reads a lot better than the index-based implementation.

clang/lib/Lex/HeaderSearch.cpp

1449–1450

Could we change this function to return an unsigned instead of Optional<unsigned> now?

Also, is &DL - &*SearchDirs.begin() safe and doesn’t trigger the issues we saw previously if start and end are allocated in different memory regions, because I don’t know.

[jansvoboda11]

clang/lib/Lex/HeaderSearch.cpp

1449–1450

Yes, updating the return type makes sense now, thanks!

Yes, this should be safe as of this patch, since we're still storing DirectoryLookup objects in std::vector<DirectoryLookup>. I'll be updating this code when we change the storage (separate std::vector<DirectoryLookup> for quoted, angled and system search paths).

[jansvoboda11]

Remove Optional<...>

[ahoppen]

clang/lib/Lex/HeaderSearch.cpp

1449–1450

OK, great. Makes sense. 👍

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;
 };
 
-/// Forward iterator over the search directories of \c HeaderSearch.
-struct ConstSearchDirIterator
-    : llvm::iterator_facade_base<ConstSearchDirIterator,
+namespace detail {
+template <bool Const, typename T>
+using Qualified = std::conditional_t<Const, const T, T>;
+
+/// Forward iterator over the search directories of HeaderSearch.
+/// Does not get invalidated by \c HeaderSearch::Add{,System}SearchPath.
+template <bool IsConst>
+struct SearchDirIteratorImpl
+    : llvm::iterator_facade_base<SearchDirIteratorImpl<IsConst>,
                                  std::forward_iterator_tag,
-                                 const DirectoryLookup> {
-  ConstSearchDirIterator(const ConstSearchDirIterator &) = default;
+                                 Qualified<IsConst, DirectoryLookup>> {
+  /// Const -> non-const iterator conversion.
+  template <typename Enable = std::enable_if<IsConst, bool>>
+  SearchDirIteratorImpl(const SearchDirIteratorImpl<false> &Other)
+      : HS(Other.HS), Idx(Other.Idx) {}
 
-  ConstSearchDirIterator &operator=(const ConstSearchDirIterator &) = default;
+  SearchDirIteratorImpl(const SearchDirIteratorImpl &) = default;
 
-  bool operator==(const ConstSearchDirIterator &RHS) const {
+  SearchDirIteratorImpl &operator=(const SearchDirIteratorImpl &) = default;
+
+  bool operator==(const SearchDirIteratorImpl &RHS) const {
     return HS == RHS.HS && Idx == RHS.Idx;
   }
 
-  ConstSearchDirIterator &operator++() {
+  SearchDirIteratorImpl &operator++() {
     assert(*this && "Invalid iterator.");
     ++Idx;
     return *this;
   }
 
-  const DirectoryLookup &operator*() const;
+  Qualified<IsConst, DirectoryLookup> &operator*() const {
+    assert(*this && "Invalid iterator.");
+    return HS->SearchDirs[Idx];
+  }
 
   /// Creates an invalid iterator.
-  ConstSearchDirIterator(std::nullptr_t) : HS(nullptr), Idx(0) {}
+  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.
-  const HeaderSearch *HS;
+  Qualified<IsConst, HeaderSearch> *HS;
 
   /// The index of the current element.
   size_t Idx;
 
   /// The constructor that creates a valid iterator.
-  ConstSearchDirIterator(const HeaderSearch &HS, size_t Idx)
+  SearchDirIteratorImpl(Qualified<IsConst, HeaderSearch> &HS, size_t Idx)
       : HS(&HS), Idx(Idx) {}
 
   /// Only HeaderSearch is allowed to instantiate valid iterators.
   friend HeaderSearch;
+
+  /// Enables const -> non-const conversion.
+  friend SearchDirIteratorImpl<!IsConst>;
 };
+} // namespace detail
+
+using ConstSearchDirIterator = detail::SearchDirIteratorImpl<true>;
+using SearchDirIterator = detail::SearchDirIteratorImpl<false>;
+
+using ConstSearchDirRange = llvm::iterator_range<ConstSearchDirIterator>;
+using SearchDirRange = llvm::iterator_range<SearchDirIterator>;
 
 /// Encapsulates the information needed to find the file referenced
 /// by a \#include or \#include_next, (sub-)framework lookup, etc.
 class HeaderSearch {
   friend class DirectoryLookup;
 
   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;
 
   DiagnosticsEngine &Diags;
public:
 
   /// 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;
 
+  SearchDirIterator search_dir_begin() { return {*this, 0}; }
+  SearchDirIterator search_dir_end() { return {*this, SearchDirs.size()}; }
+  SearchDirRange search_dir_range() {
+    return {search_dir_begin(), search_dir_end()};
+  }
+
   ConstSearchDirIterator search_dir_begin() const { return quoted_dir_begin(); }
   ConstSearchDirIterator search_dir_end() const { return system_dir_end(); }
+  ConstSearchDirRange search_dir_range() const {
+    return {search_dir_begin(), search_dir_end()};
+  }
 
   unsigned search_dir_size() const { return SearchDirs.size(); }
 
   ConstSearchDirIterator quoted_dir_begin() const { return {*this, 0}; }
   ConstSearchDirIterator quoted_dir_end() const { return angled_dir_begin(); }
 
   ConstSearchDirIterator angled_dir_begin() const {
     return {*this, AngledDirIdx};
   }
   ConstSearchDirIterator angled_dir_end() const { return system_dir_begin(); }
 
   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.
-  Optional<unsigned> searchDirIdx(const DirectoryLookup &DL) const;
+  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

clang/lib/Lex/HeaderSearch.cpp

if (!ControllingMacroID || !External)
     return nullptr;
 
   ControllingMacro = External->GetIdentifier(ControllingMacroID);
   return ControllingMacro;
 }
 
 ExternalHeaderFileInfoSource::~ExternalHeaderFileInfoSource() = default;
 
-const DirectoryLookup &ConstSearchDirIterator::operator*() const {
-  assert(*this && "Invalid iterator.");
-  return HS->SearchDirs[Idx];
-}
-
 HeaderSearch::HeaderSearch(std::shared_ptr<HeaderSearchOptions> HSOpts,
                            SourceManager &SourceMgr, DiagnosticsEngine &Diags,
                            const LangOptions &LangOpts,
                            const TargetInfo *Target)
     : HSOpts(std::move(HSOpts)), Diags(Diags),
       FileMgr(SourceMgr.getFileManager()), FrameworkMap(64),
       ModMap(SourceMgr, Diags, LangOpts, Target, *this) {}
 
Module = lookupModule(ModuleName, SearchName, ImportLoc,
                           AllowExtraModuleMapSearch);
   return Module;
 }
 
 Module *HeaderSearch::lookupModule(StringRef ModuleName, StringRef SearchName,
                                    SourceLocation ImportLoc,
                                    bool AllowExtraModuleMapSearch) {
   Module *Module = nullptr;
-  unsigned Idx;
+  SearchDirIterator It = 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 (It = search_dir_begin(); It != search_dir_end(); ++It) {
+    if (It->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 += It->getFrameworkDir()->getName();
       llvm::sys::path::append(FrameworkDirName, SearchName + ".framework");
       if (auto FrameworkDir = FileMgr.getDirectory(FrameworkDirName)) {
-        bool IsSystem
-          = SearchDirs[Idx].getDirCharacteristic() != SrcMgr::C_User;
+        bool IsSystem = It->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 (!It->isNormalDir())
       continue;
 
-    bool IsSystem = SearchDirs[Idx].isSystemHeaderDirectory();
+    bool IsSystem = It->isSystemHeaderDirectory();
     // Search for a module map file in this directory.
-    if (loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
+    if (loadModuleMapFile(It->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 = It->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 (It->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(*It);
 
     // Look again for the module.
     Module = ModMap.findModule(ModuleName);
     if (Module)
       break;
   }
 
   if (Module)
-    noteLookupUsage(Idx, ImportLoc);
+    noteLookupUsage(It.Idx, 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(HS.searchDirIdx(*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

 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;
+unsigned HeaderSearch::searchDirIdx(const DirectoryLookup &DL) const {
+  return &DL - &*SearchDirs.begin();
 }
 
 StringRef HeaderSearch::getUniqueFrameworkName(StringRef Framework) {
   return FrameworkNames.insert(Framework).first->first();
 }
 
 bool HeaderSearch::hasModuleMap(StringRef FileName,
                                 const DirectoryEntry *Root,
HeaderSearch::loadModuleMapFile(const DirectoryEntry *Dir, bool IsSystem,
   return LMM_InvalidModuleMap;
 }
 
 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()) {
+    for (DirectoryLookup &DL : search_dir_range()) {
+      bool IsSystem = DL.isSystemHeaderDirectory();
+      if (DL.isFramework()) {
         std::error_code EC;
         SmallString<128> DirNative;
-        llvm::sys::path::native(SearchDirs[Idx].getFrameworkDir()->getName(),
-                                DirNative);
+        llvm::sys::path::native(DL.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 (DL.isHeaderMap())
         continue;
 
       // Try to load a module map file for the search directory.
-      loadModuleMapFile(SearchDirs[Idx].getDir(), IsSystem,
-                        /*IsFramework*/ false);
+      loadModuleMapFile(DL.getDir(), IsSystem, /*IsFramework*/ false);
 
       // Try to load module map files for immediate subdirectories of this
       // search directory.
-      loadSubdirectoryModuleMaps(SearchDirs[Idx]);
+      loadSubdirectoryModuleMaps(DL);
     }
   }
 
   // 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) {
+  for (const DirectoryLookup &DL : search_dir_range()) {
     // We only care about normal header directories.
-    if (!SearchDirs[Idx].isNormalDir()) {
+    if (!DL.isNormalDir())
       continue;
-    }
 
     // Try to load a module map file for the search directory.
-    loadModuleMapFile(SearchDirs[Idx].getDir(),
-                      SearchDirs[Idx].isSystemHeaderDirectory(),
-                      SearchDirs[Idx].isFramework());
+    loadModuleMapFile(DL.getDir(), DL.isSystemHeaderDirectory(),
+                      DL.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();
+  for (const DirectoryLookup &DL : search_dir_range()) {
+    if (DL.isNormalDir()) {
+      StringRef Dir = DL.getDir()->getName();
       if (CheckDir(Dir)) {
         if (IsSystem)
-          *IsSystem = BestPrefixLength ? I >= SystemDirIdx : false;
+          *IsSystem = BestPrefixLength && isSystem(DL.getDirCharacteristic());
         BestPrefixIsFramework = false;
       }
-    } else if (SearchDirs[I].isFramework()) {
-      StringRef Dir = SearchDirs[I].getFrameworkDir()->getName();
+    } else if (DL.isFramework()) {
+      StringRef Dir = DL.getFrameworkDir()->getName();
       if (CheckDir(Dir)) {
         if (IsSystem)
-          *IsSystem = BestPrefixLength ? I >= SystemDirIdx : false;
+          *IsSystem = BestPrefixLength && isSystem(DL.getDirCharacteristic());
         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())
+  for (const DirectoryLookup &DL : search_dir_range()) {
+    if (!DL.isHeaderMap())
       continue;
 
     StringRef SpelledFilename =
-        SearchDirs[I].getHeaderMap()->reverseLookupFilename(Filename);
+        DL.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