[clang] refactor FileManager::GetUniqueIDMapping

[rmaz]

Summary

Refactor FileManager::GetUniqueIDMapping to populate an array of
OptionalFileEntryRefDegradesToFileEntryPtr instead of UID to
FileEntry *. This should allow the path serialization of input files
to use the paths used when looking up a file entry, instead of the
last reference.

Per the FileManager documentation, VirtualFileEntries is a subset of
SeenFileEntries. This means we only have to iterate over the latter
to create a complete UID mapping.

[rmaz]

Sort by UIDs, then Name

[jansvoboda11]

clang/include/clang/Basic/FileManager.h

314

Since we're already modifying the two only users of this function, maybe we could use Optional<FileEntryRef> instead of OptionalFileEntryRefDegradesToFileEntryPtr (which we want to eventually remove)?

clang/lib/Basic/FileManager.cpp

623–625

Why is this necessary? IIUC, FileEntryRef has this logic in getBaseMapEntry(). I would expect FileEntryRef(Entry) to be correct regardless of what's in Value->V.

clang/lib/Serialization/ASTWriter.cpp

175

I'm afraid that iterating over file entries in "non-deterministic" order can cause non-determinism down the line. For example, calling HeaderSearch::findAllModulesForHeader() in the loop can trigger deserialization of HeaderFileInfo from loaded PCMs. That code fills the Module::Headers vectors, which we serialize without sorting first.

1918–1921

Nit: I'd slightly prefer:

if (A->getUID() != B->getUID())
  return A->getUID() < B->getUID();

return A->getName() < B->getName();

[jansvoboda11]

In general, I think this approach makes sense.

clang/lib/Serialization/ASTWriter.cpp

1917

Nit: Probably not necessary to take FileEntryRef by reference.

1931

This will insert duplicate entries (with the same key) into the on-disk hash table. I don't know if that's problematic, just thought I'd call it out.

[rmaz]

clang/include/clang/Basic/FileManager.h

314

We could do that with less churn once more or the called methods in the loop over the files are refactored in D142724, but I'm fine with either approach.

clang/lib/Basic/FileManager.cpp

623–625

I borrowed this from: https://github.com/llvm/llvm-project/blob/main/clang/lib/Basic/FileManager.cpp#L399-L408

I assumed this was necessary from @benlangmuir 's comment on D142780:

Also, it will never give you a vfs mapped path since it's skipping those (V.dyn_cast<FileEntry *>()).

Are you saying we should just do something like:

for (const auto &Entry : SeenFileEntries) {
    if (llvm::ErrorOr<FileEntryRef::MapValue> Value = Entry.getValue())
        Entries.push_back(FileEntryRef(Entry));
}

?

clang/lib/Serialization/ASTWriter.cpp

175

Do you think we should move the sorting into the getSeenFileEntries() method?

1931

Not sure I follow, why would we have FileEntrys with duplicate names?

[jansvoboda11]

clang/lib/Basic/FileManager.cpp

623–625

Oh, okay, so the goal is to skip VFS-mapped file entries and only serialize the on-disk ones into PCMs. That makes sense given we do actual FileEntry comparison in HeaderFileInfoTrait::EqualKey() (instead of plain comparison of filenames that I assumed). I think that for VFS-mapped entries, we always have a separate element in the SeenFileEntries map that represents the on-disk file entry. So we should be skipping the VFS-mapped entries entirely instead of considering their remapping target entries again.

If my understanding is correct, we should do something like this:

if (llvm::ErrorOr<FileEntryRef::MapValue> Value = Entry.getValue())
  // Ignore VFS-mapped entries.
  if (Value->V.dyn_cast<FileEntry *>())
    Entries.push_back(FileEntryRef(Entry));

clang/lib/Serialization/ASTWriter.cpp

175

I think so, yes.

1931

Sorry, I had assumed we only do lookups in the on-disk hash table based on filenames (instead of full FileEntry comparison) and that for that reason, we should serialize all FileEntryRef into the PCM, even the VFS-mapped ones. But I now see that you're trying to only serialize the on-disk FileEntryRefs, which will not cause duplication. Ignore my comment here.

[rmaz]

Don't return virtual file entries

[jansvoboda11]

clang/include/clang/Basic/FileManager.h

314

Hmm, thinking about this more, it doesn't make sense for this function to return empty Optional<FileEntryRef>. Changing the parameter type to SmallVectorImpl<FileEntryRef> & and updating the clients to use . instead of -> is the most clear/correct option IMO.

I think the function name & documentation should point out that we're only returning files non-vfs-redirected files (and vfs-redirected files that don't use the external name).

clang/lib/Basic/FileManager.cpp

20

Already included in FileManager.h.

clang/lib/Serialization/ASTWriter.cpp

39

Already provided by FileManager.h.

[jansvoboda11]

clang/lib/Basic/FileManager.cpp

623

Nit: I think dyn_cast() could be replaced by is().

[rmaz]

Use FileEntryRef, rename method

[benlangmuir]

This should allow the path serialization of input files to use the paths used when looking up a file entry, instead of the last reference.

Isn't this at odds with not having the VFS-mapped paths?

It's not obvious to me why we want these specific semantics. Elsewhere we have tried to preserve the virtual paths as well as the vfsoverlay files needed to interpret them. Is there a reason the current approach is better? I feel like there may be context here I'm lacking

[rmaz]

In D143414#4110461, @benlangmuir wrote:

This should allow the path serialization of input files to use the paths used when looking up a file entry, instead of the last reference.

Isn't this at odds with not having the VFS-mapped paths?

It's not obvious to me why we want these specific semantics. Elsewhere we have tried to preserve the virtual paths as well as the vfsoverlay files needed to interpret them. Is there a reason the current approach is better? I feel like there may be context here I'm lacking

My understanding for why we were dropping the virtual paths is that we would already have the on-disk path entries anyway, but @jansvoboda11 may know more.

The reason for the change from FileEntry to FileEntryRef is so we can produce deterministic pcm output regardless of if the files are regular files or hard links pointing to the same inode. Currently this can result in varying paths and numbers of inputs being serialized.

[benlangmuir]

+1 for determinism. Okay I spent some time trying to understand how this code is used and the non-virtual paths make some sense now. I am a bit skeptical about this on-disk-hash-table by filepath but that's separate from this patch.

clang/lib/Serialization/ASTWriter.cpp

175

I think you can remove header_file_size.

[rmaz]

remove header_file_size()

clang/include/clang/Basic/FileManager.h

public:
   /// \returns true if \c path changed.
   bool FixupRelativePath(SmallVectorImpl<char> &path) const;
 
   /// Makes \c Path absolute taking into account FileSystemOptions and the
   /// working directory option.
   /// \returns true if \c Path changed to absolute.
   bool makeAbsolutePath(SmallVectorImpl<char> &Path) const;
 
-  /// Produce an array mapping from the unique IDs assigned to each
-  /// file to the corresponding FileEntry pointer.
-  void GetUniqueIDMapping(
-                    SmallVectorImpl<const FileEntry *> &UIDToFiles) const;
+  /// Produce an array of seen FileEntryRef. The entries will be sorted
+  /// by UID and Name. Virtual file entries will not be returned.
+  void
+  getSeenNonVirtualFileEntries(SmallVectorImpl<FileEntryRef> &Entries) const;
 
   /// Retrieve the canonical name for a given directory.
   ///
   /// This is a very expensive operation, despite its results being cached,
   /// and should only be used when the physical layout of the file system is
   /// required, which is (almost) never.
   StringRef getCanonicalName(const DirectoryEntry *Dir);
 

clang/include/clang/Lex/HeaderSearch.h

 
 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).

clang/lib/Basic/FileManager.cpp

 //
 // TODO: This should index all interesting directories with dirent calls.
 //  getdirentries ?
 //  opendir/readdir_r/closedir ?
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/FileSystemStatCache.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
FileManager::getNoncachedStatValue(StringRef Path,
 
   llvm::ErrorOr<llvm::vfs::Status> S = FS->status(FilePath.c_str());
   if (!S)
     return S.getError();
   Result = *S;
   return std::error_code();
 }
 
-void FileManager::GetUniqueIDMapping(
-    SmallVectorImpl<const FileEntry *> &UIDToFiles) const {
-  UIDToFiles.clear();
-  UIDToFiles.resize(NextFileUID);
-
-  // Map file entries
-  for (llvm::StringMap<llvm::ErrorOr<FileEntryRef::MapValue>,
-                       llvm::BumpPtrAllocator>::const_iterator
-           FE = SeenFileEntries.begin(),
-           FEEnd = SeenFileEntries.end();
-       FE != FEEnd; ++FE)
-    if (llvm::ErrorOr<FileEntryRef::MapValue> Entry = FE->getValue()) {
-      if (const auto *FE = Entry->V.dyn_cast<FileEntry *>())
-        UIDToFiles[FE->getUID()] = FE;
-    }
-
-  // Map virtual file entries
-  for (const auto &VFE : VirtualFileEntries)
-    UIDToFiles[VFE->getUID()] = VFE;
+void FileManager::getSeenNonVirtualFileEntries(
+    SmallVectorImpl<FileEntryRef> &Entries) const {
+  Entries.reserve(SeenFileEntries.size());
+
+  for (const auto &Entry : SeenFileEntries) {
+    if (auto Value = Entry.getValue())
+      // Ignore VFS-mapped entries, they will have a separate on-disk
+      // file entry.
+      if (Value->V.is<FileEntry *>())
+        Entries.push_back(FileEntryRef(Entry));
+  }
+
+  // We want the file entries in deterministic order for
+  // module serialization.
+  llvm::sort(Entries, [](FileEntryRef &A, FileEntryRef &B) {
+    if (A.getUID() != B.getUID())
+      return A.getUID() < B.getUID();
+
+    return A.getName() < B.getName();
+  });
 }
 
 StringRef FileManager::getCanonicalName(const DirectoryEntry *Dir) {
   llvm::DenseMap<const void *, llvm::StringRef>::iterator Known
     = CanonicalNames.find(Dir);
   if (Known != CanonicalNames.end())
     return Known->second;
 

clang/lib/Serialization/ASTWriter.cpp

 #include "clang/AST/NestedNameSpecifier.h"
 #include "clang/AST/OpenMPClause.h"
 #include "clang/AST/RawCommentList.h"
 #include "clang/AST/TemplateName.h"
 #include "clang/AST/Type.h"
 #include "clang/AST/TypeLocVisitor.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/FileSystemOptions.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/Lambda.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/Module.h"
 #include "clang/Basic/ObjCRuntime.h"
 #include "clang/Basic/OpenCLOptions.h"

 std::set<const FileEntry *> GetAffectingModuleMaps(const Preprocessor &PP,
                                                    Module *RootModule) {
   std::set<const FileEntry *> ModuleMaps{};
   std::set<const Module *> ProcessedModules;
   SmallVector<const Module *> ModulesToProcess{RootModule};
 
   const HeaderSearch &HS = PP.getHeaderSearchInfo();
 
-  SmallVector<const FileEntry *, 16> FilesByUID;
-  HS.getFileMgr().GetUniqueIDMapping(FilesByUID);
-
-  if (FilesByUID.size() > HS.header_file_size())
-    FilesByUID.resize(HS.header_file_size());
-
-  for (unsigned UID = 0, LastUID = FilesByUID.size(); UID != LastUID; ++UID) {
-    const FileEntry *File = FilesByUID[UID];
-    if (!File)
-      continue;
+  SmallVector<FileEntryRef, 16> FileEntries;
+  HS.getFileMgr().getSeenNonVirtualFileEntries(FileEntries);
 
+  for (auto File : FileEntries) {
     const HeaderFileInfo *HFI =
         HS.getExistingFileInfo(File, /*WantExternal*/ false);
     if (!HFI || (HFI->isModuleHeader && !HFI->isCompilingModuleHeader))
       continue;
 
     for (const auto &KH : HS.findAllModulesForHeader(File)) {
       if (!KH.getModule())
         continue;
while (!Worklist.empty()) {
         Generator.insert(Key, Data, GeneratorTrait);
         ++NumHeaderSearchEntries;
       }
 
       Worklist.append(M->submodule_begin(), M->submodule_end());
     }
   }
 
-  SmallVector<const FileEntry *, 16> FilesByUID;
-  HS.getFileMgr().GetUniqueIDMapping(FilesByUID);
+  SmallVector<FileEntryRef, 16> FileEntries;
+  HS.getFileMgr().getSeenNonVirtualFileEntries(FileEntries);
 
-  if (FilesByUID.size() > HS.header_file_size())
-    FilesByUID.resize(HS.header_file_size());
-
-  for (unsigned UID = 0, LastUID = FilesByUID.size(); UID != LastUID; ++UID) {
-    const FileEntry *File = FilesByUID[UID];
-    if (!File)
-      continue;
+  for (auto File : FileEntries) {
 
     // Get the file info. This will load info from the external source if
     // necessary. Skip emitting this file if we have no information on it
     // as a header file (in which case HFI will be null) or if it hasn't
     // changed since it was loaded. Also skip it if it's for a modular header
     // from a different module; in that case, we rely on the module(s)
     // containing the header to provide this information.
     const HeaderFileInfo *HFI =
         HS.getExistingFileInfo(File, /*WantExternal*/!Chain);
     if (!HFI || (HFI->isModuleHeader && !HFI->isCompilingModuleHeader))
       continue;
 
     // Massage the file path into an appropriate form.
-    StringRef Filename = File->getName();
+    StringRef Filename = File.getName();
     SmallString<128> FilenameTmp(Filename);
     if (PreparePathForOutput(FilenameTmp)) {
       // If we performed any translation on the file name at all, we need to
       // save this string, since the generator will refer to it later.
       Filename = StringRef(strdup(FilenameTmp.c_str()));
       SavedStrings.push_back(Filename.data());
     }
 
-    HeaderFileInfoTrait::key_type Key = {
-      Filename, File->getSize(), getTimestampForOutput(File)
-    };
+    HeaderFileInfoTrait::key_type Key = {Filename, File.getSize(),
+                                         getTimestampForOutput(File)};
     HeaderFileInfoTrait::data_type Data = {
       *HFI, HS.getModuleMap().findResolvedModulesForHeader(File), {}
     };
     Generator.insert(Key, Data, GeneratorTrait);
     ++NumHeaderSearchEntries;
   }
 
   // Create the on-disk hash table in a buffer.