[llvm][vfs] For virtual directories, use the virtual path as the real path

[jansvoboda11]

Summary

A follow-up to D135841. This patch returns the virtual path for directories from RedirectingFileSystem. This ensures the contents of Path are the same as the contents of FS->getRealPath(Path). This also means we can drop the workaround in Clang's module map canonicalization, where we couldn't use the real path for a directory if it resolved to a different DirectoryEntry. In addition to that, we can also avoid introducing new workaround for a bug triggered by the newly introduced test case.

[jansvoboda11]

Return canonical virtual path from RedirectingFileSystem

[jansvoboda11]

Module map canonicalization in clang-scan-deps causes issues even after D135841 landed.

Here's the problematic scenario this patch aims to solve:

• there is a framework FW whose headers (but not module maps) are redirected in a VFS overlay file
• there is a TU with #import <fw/Header.h> (note the incorrect case of the framework name)
• what follows is how Clang treats the involved file/directory paths:
  • find the incorrectly-cased header through the case-insensitive VFS overlay
  • chop off Headers/Header.h
  • call FileManager::getCanonicalName() on the fw.framework directory
    • RedirectingFileSystem calls the underlying FS to get the real path
      • note: this happens since the node is not RedirectingFileSystem::{FileEntry,DirectoryRemapEntry}, see the last branch of RedirectingFileSystem::getRealPath()
      • the underlying case-sensitive FS doesn't recognize the incorrectly-cased path
    • FileManager falls back to just using Dir.getName() (fw.framework) for that virtual DirectoryEntry as the canonical path
  • the fw.framework/Modules/module.modulemap file is not in the VFS overlay, and due to the wrong case, the underlying case-sensitive FW doesn't recognize it either
  • no matching module map means #include <fw/Header.h> is resolved to textual include
  • that header then includes other headers from the same FW using correct case: #import <FW/AnotherHeader.h>
  • the correctly-cased module map is found in the underlying FS and the framework gets compiled into a PCM file
  • at the end of dependency scan, scanner takes the correctly-cased module map path from the PCM file
  • scanner tries to canonicalize the module map path
    • Modules/module.modulemap is chopped off and FileManager::getCanonicalName() is called on the framework directory
    • FileManager::getDirectory("FW.framework") resolves to the same DirectoryEntry that fw.framework resolved to (VFS overlay is case-insensitive)
    • FileManager looks in the cache of canonical names and finds fw.framework for that virtual DirectoryEntry
    • FW.framework/Modules/module.modulemap is canonicalized to fw.framework/Modules/module.modulemap
  • scanner asserts that file exists, but it's not in the VFS nor in the underlying case-sensitive FS

This patch fixes this issue by returning the canonical virtual path for fw.framework at the very beginning. This is achieved by using the as-written spelling from the overlay file.

I can think of two other alternatives to this patch:

• In ModuleMap::canonicalizeModuleMapPath(), avoid canonicalization if the new module map path resolves to a different (or no) FileEntry.
• In FileManager, cache real paths based on the directory name, not the DirectoryEntry.

Both of these alternatives are workarounds, whereas the VFS fix seems fairly straightforward.

Note that I plan to add unit tests for this and add // XFAIL: case-insensitive-filesystem to the clang-scan-deps test if we get consensus on this approach.

[jansvoboda11]

Just realized this most likely won't work if the case-insensitive VFS is specified with wrong spelling too, e.g. Fw.framework. Maybe we'll need to combine this patch with one of the alternatives after all.

[benlangmuir]

Just realized this most likely won't work if the case-insensitive VFS is specified with wrong spelling too, e.g. Fw.framework.

Is this about the spelling in the VFS definition itself, or about the path being looked up? If it's the VFS definition maybe we can say that's a bug for whoever wrote the VFS? Ideally we could diagnose but I'm not sure we want to pay for a lot of calls to realpath.

llvm/include/llvm/Support/VirtualFileSystem.h

876

SmallVector?

[jansvoboda11]

In D135849#4464234, @benlangmuir wrote:

Just realized this most likely won't work if the case-insensitive VFS is specified with wrong spelling too, e.g. Fw.framework.

Is this about the spelling in the VFS definition itself, or about the path being looked up?

Yes, spelling in the VFS definition itself.

If it's the VFS definition maybe we can say that's a bug for whoever wrote the VFS? Ideally we could diagnose but I'm not sure we want to pay for a lot of calls to realpath.

You mean diagnosing whenever the spelling in the VFS definition differs from its realpath? How could we make that work with symlinks in place?

[benlangmuir]

You mean diagnosing whenever the spelling in the VFS definition differs from its realpath?

Right, this would be ideal, but may be too expensive in practice.

How could we make that work with symlinks in place?

Ah right, we are intentionally allowing symlinks in the VFS path (e.g. Foo.framework/Headers) because we don't correctly handle symlink resolution in the VFS itself.

You can get the canonical spelling of a symlink in a couple of ways: you can readdir the parent directory and find all case-insensitive matches. If there is only 1, that's the spelling, if there are more than 1 then it's a case-sensitive filesystem and the original path must be correct. Another way that is OS-specific is on Darwin you can open(..., O_SYMLINK) the path component to open the symlink itself and then fcntl(..., F_GETPATH, ...) to get its realpath. Both of these approaches require handling each component of the path individually, though each step is cacheable. Not sure if there are any better ways.

As I said, not sure we can afford to diagnose this.

[jansvoboda11]

Okay, I'll try to figure out how expensive this would be. I'd like Clang to be stricter in situations like these, but if that's not feasible, I'll probably implement the first workaround.

For the second workaround, I don't think that moves us in better direction - we should be able to assign one canonical real path to each DirectoryEntry.

The unfortunate aspect of the ModuleMap::canonicalizeModuleMapPath() implementation is that it uses FileManager.getDirectoryRef(llvm::sys::path::parent_path(ModuleMapFilePath)). If the request for getting the module map file fell through the VFS into the underlying FS, parent DirectoryEntry of that file is different than the virtual directory made for the VFS. Chopping off the file name and going through the VFS again doesn't guarantee falling through the VFS again, which that code doesn't account for. It'd be really nice to have DirectoryEntry::getDir() API, so that we can walk up the directory hierarchy while preserving the virtual/real distinction between directories in the overlay/on disk, never accidentally "bubbling up" into the overlay again. What's your take on that?

[benlangmuir]

In D135849#4469347, @jansvoboda11 wrote:

It'd be really nice to have DirectoryEntry::getDir() API, so that we can walk up the directory hierarchy while preserving the virtual/real distinction between directories in the overlay/on disk, never accidentally "bubbling up" into the overlay again. What's your take on that?

Can you say more about how you would do this and preserve the real/virtual distinction? Currently FileManager is just filling in the directory based on the parent path with a lookup to the VFS, so isn't it the same issue? Or did you mean we would keep more info?

[jansvoboda11]

In D135849#4469376, @benlangmuir wrote:

In D135849#4469347, @jansvoboda11 wrote:

It'd be really nice to have DirectoryEntry::getDir() API, so that we can walk up the directory hierarchy while preserving the virtual/real distinction between directories in the overlay/on disk, never accidentally "bubbling up" into the overlay again. What's your take on that?

Can you say more about how you would do this and preserve the real/virtual distinction? Currently FileManager is just filling in the directory based on the parent path with a lookup to the VFS, so isn't it the same issue? Or did you mean we would keep more info?

Yes, the mechanism you mention has the same issue. My idea was that we could keep more information when looking up the path in the VFS, associate each {File,Directory}Entry with list of FileSystem * that "owns" each of its parent directories. We could then send the llvm::sys::path::parent_path(...) argument directly to the owning FS instead to the top one. This is not realistic from performance standpoint, though.

[jansvoboda11]

Add unit tests, use SmallVector, make clang-scan-deps test portable

[jansvoboda11]

I think this patch should now stand on its own. Dealing with a VFS definition that uses the wrong case for virtual paths is not necessary for correctness. If Clang asks the FS for a file using the correct case, the query either fails and we never get far enough to need module map path canonicalization, or the query succeeds thanks to case-insensitivity of the VFS and canonicalizing to the VFS spelling means all future queries using it will succeed as well.

clang/lib/Lex/ModuleMap.cpp

ModuleMap::canonicalizeModuleMapPath(SmallVectorImpl<char> &Path) {
 
   FileManager &FM = SourceMgr.getFileManager();
   auto DirEntry = FM.getDirectoryRef(Dir.empty() ? "." : Dir);
   if (!DirEntry)
     return llvm::errorToErrorCode(DirEntry.takeError());
 
   // Canonicalize the directory.
   StringRef CanonicalDir = FM.getCanonicalName(*DirEntry);
-  if (CanonicalDir != Dir) {
-    auto CanonicalDirEntry = FM.getDirectory(CanonicalDir);
-    // Only use the canonicalized path if it resolves to the same entry as the
-    // original. This is not true if there's a VFS overlay on top of a FS where
-    // the directory is a symlink. The overlay would not remap the target path
-    // of the symlink to the same directory entry in that case.
-    if (CanonicalDirEntry && *CanonicalDirEntry == *DirEntry) {
-      bool Done = llvm::sys::path::replace_path_prefix(Path, Dir, CanonicalDir);
-      (void)Done;
-      assert(Done && "Path should always start with Dir");
-    }
-  }
+  if (CanonicalDir != Dir)
+    llvm::sys::path::replace_path_prefix(Path, Dir, CanonicalDir);
 
   // In theory, the filename component should also be canonicalized if it
   // on a case-insensitive filesystem. However, the extra canonicalization is
   // expensive and if clang looked up the filename it will always be lowercase.
 
   // Remove ., remove redundant separators, and switch to native separators.
   // This is needed for separators between CanonicalDir and the filename.
   llvm::sys::path::remove_dots(Path);

clang/test/ClangScanDeps/modules-canononical-module-map-case.c

+// This test checks that VFS-mapped module map path has the correct spelling
+// after canonicalization, even if it was first accessed using different case.
+
+// RUN: rm -rf %t
+// RUN: split-file %s %t
+
+//--- actual/One.h
+#import <FW/Two.h>
+//--- actual/Two.h
+// empty
+//--- frameworks/FW.framework/Modules/module.modulemap
+framework module FW {
+  header "One.h"
+  header "Two.h"
+}
+//--- tu.m
+#import <fw/One.h>
+
+//--- overlay.json.in
+{
+  "version": 0,
+  "case-sensitive": "false",
+  "roots": [
+    {
+      "contents": [
+        {
+          "external-contents": "DIR/actual/One.h",
+          "name": "One.h",
+          "type": "file"
+        },
+        {
+          "external-contents": "DIR/actual/Two.h",
+          "name": "Two.h",
+          "type": "file"
+        }
+      ],
+      "name": "DIR/frameworks/FW.framework/Headers",
+      "type": "directory"
+    }
+  ]
+}
+
+//--- cdb.json.in
+[{
+  "directory": "DIR",
+  "file": "DIR/tu.m",
+  "command": "clang -fmodules -fmodules-cache-path=DIR/cache -ivfsoverlay DIR/overlay.json -F DIR/frameworks -c DIR/tu.m -o DIR/tu.o"
+}]
+
+// RUN: sed -e "s|DIR|%/t|g" %t/cdb.json.in > %t/cdb.json
+// RUN: sed -e "s|DIR|%/t|g" %t/overlay.json.in > %t/overlay.json
+// RUN: clang-scan-deps -compilation-database %t/cdb.json -format experimental-full > %t/result.json
+// RUN: cat %t/result.json | sed 's:\\\\\?:/:g' | FileCheck %s -DPREFIX=%/t
+
+// CHECK:      {
+// CHECK-NEXT:   "modules": [
+// CHECK-NEXT:     {
+// CHECK-NEXT:       "clang-module-deps": [],
+// CHECK-NEXT:       "clang-modulemap-file": "[[PREFIX]]/frameworks/FW.framework/Modules/module.modulemap",
+// CHECK-NEXT:       "command-line": [
+// CHECK:              "-x"
+// CHECK-NEXT:         "objective-c"
+// CHECK-NEXT:         "[[PREFIX]]/frameworks/FW.framework/Modules/module.modulemap"
+// CHECK:            ],
+// CHECK-NEXT:       "context-hash": "{{.*}}",
+// CHECK-NEXT:       "file-deps": [
+// CHECK:            ],
+// CHECK-NEXT:       "name": "FW"
+// CHECK-NEXT:     }
+// CHECK-NEXT:   ]
+// CHECK:      }

llvm/include/llvm/Support/VirtualFileSystem.h

public:
     FileEntry(StringRef Name, StringRef ExternalContentsPath, NameKind UseName)
         : RemapEntry(EK_File, Name, ExternalContentsPath, UseName) {}
 
     static bool classof(const Entry *E) { return E->getKind() == EK_File; }
   };
 
   /// Represents the result of a path lookup into the RedirectingFileSystem.
   struct LookupResult {
+    /// Chain of parent directory entries for \c E.
+    llvm::SmallVector<Entry *, 32> Parents;
+
     /// The entry the looked-up path corresponds to.
     Entry *E;
 
   private:
     /// When the found Entry is a DirectoryRemapEntry, stores the path in the
     /// external file system that the looked-up path in the virtual file system
     //  corresponds to.
     std::optional<std::string> ExternalRedirect;
 
   public:
     LookupResult(Entry *E, sys::path::const_iterator Start,
                  sys::path::const_iterator End);
 
     /// If the found Entry maps the the input path to a path in the external
     /// file system (i.e. it is a FileEntry or DirectoryRemapEntry), returns
     /// that path.
     std::optional<StringRef> getExternalRedirect() const {
       if (isa<DirectoryRemapEntry>(E))
         return StringRef(*ExternalRedirect);
       if (auto *FE = dyn_cast<FileEntry>(E))
         return FE->getExternalContentsPath();
       return std::nullopt;
     }
+
+    /// Get the (canonical) path of the found entry. This uses the as-written
+    /// path components from the VFS specification.
+    void getPath(llvm::SmallVectorImpl<char> &Path) const;
   };
 
 private:
   friend class RedirectingFSDirIterImpl;
   friend class RedirectingFileSystemParser;
 
   /// Canonicalize path by removing ".", "..", "./", components. This is
   /// a VFS request, do not bother about symlinks in the path components
private:
   /// @}
 
   RedirectingFileSystem(IntrusiveRefCntPtr<FileSystem> ExternalFS);
 
   /// Looks up the path <tt>[Start, End)</tt> in \p From, possibly recursing
   /// into the contents of \p From if it is a directory. Returns a LookupResult
   /// giving the matched entry and, if that entry is a FileEntry or
   /// DirectoryRemapEntry, the path it redirects to in the external file system.
-  ErrorOr<LookupResult> lookupPathImpl(llvm::sys::path::const_iterator Start,
-                                       llvm::sys::path::const_iterator End,
-                                       Entry *From) const;
+  ErrorOr<LookupResult>
+  lookupPathImpl(llvm::sys::path::const_iterator Start,
+                 llvm::sys::path::const_iterator End, Entry *From,
+                 llvm::SmallVectorImpl<Entry *> &Entries) const;
 
   /// Get the status for a path with the provided \c LookupResult.
   ErrorOr<Status> status(const Twine &CanonicalPath, const Twine &OriginalPath,
                          const LookupResult &Result);
 
 public:
   /// Looks up \p Path in \c Roots and returns a LookupResult giving the
   /// matched entry and, if the entry was a FileEntry or DirectoryRemapEntry,

llvm/lib/Support/VirtualFileSystem.cpp

RedirectingFileSystem::LookupResult::LookupResult(
   if (auto *DRE = dyn_cast<RedirectingFileSystem::DirectoryRemapEntry>(E)) {
     SmallString<256> Redirect(DRE->getExternalContentsPath());
     sys::path::append(Redirect, Start, End,
                       getExistingStyle(DRE->getExternalContentsPath()));
     ExternalRedirect = std::string(Redirect);
   }
 }
 
+void RedirectingFileSystem::LookupResult::getPath(
+    llvm::SmallVectorImpl<char> &Result) const {
+  Result.clear();
+  for (Entry *Parent : Parents)
+    llvm::sys::path::append(Result, Parent->getName());
+  llvm::sys::path::append(Result, E->getName());
+}
+
 std::error_code
 RedirectingFileSystem::makeCanonical(SmallVectorImpl<char> &Path) const {
   if (std::error_code EC = makeAbsolute(Path))
     return EC;
 
   llvm::SmallString<256> CanonicalPath =
       canonicalize(StringRef(Path.data(), Path.size()));
   if (CanonicalPath.empty())
     return make_error_code(llvm::errc::invalid_argument);
 
   Path.assign(CanonicalPath.begin(), CanonicalPath.end());
   return {};
 }
 
 ErrorOr<RedirectingFileSystem::LookupResult>
 RedirectingFileSystem::lookupPath(StringRef Path) const {
   sys::path::const_iterator Start = sys::path::begin(Path);
   sys::path::const_iterator End = sys::path::end(Path);
+  llvm::SmallVector<Entry *, 32> Entries;
   for (const auto &Root : Roots) {
     ErrorOr<RedirectingFileSystem::LookupResult> Result =
-        lookupPathImpl(Start, End, Root.get());
-    if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
+        lookupPathImpl(Start, End, Root.get(), Entries);
+    if (Result || Result.getError() != llvm::errc::no_such_file_or_directory) {
+      Result->Parents = std::move(Entries);
       return Result;
     }
+  }
   return make_error_code(llvm::errc::no_such_file_or_directory);
 }
 
 ErrorOr<RedirectingFileSystem::LookupResult>
 RedirectingFileSystem::lookupPathImpl(
     sys::path::const_iterator Start, sys::path::const_iterator End,
-    RedirectingFileSystem::Entry *From) const {
+    RedirectingFileSystem::Entry *From,
+    llvm::SmallVectorImpl<Entry *> &Entries) const {
   assert(!isTraversalComponent(*Start) &&
          !isTraversalComponent(From->getName()) &&
          "Paths should not contain traversal components");
 
   StringRef FromName = From->getName();
 
   // Forward the search to the next component in case this is an empty one.
   if (!FromName.empty()) {
if (isa<RedirectingFileSystem::FileEntry>(From))
     return make_error_code(llvm::errc::not_a_directory);
 
   if (isa<RedirectingFileSystem::DirectoryRemapEntry>(From))
     return LookupResult(From, Start, End);
 
   auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(From);
   for (const std::unique_ptr<RedirectingFileSystem::Entry> &DirEntry :
        llvm::make_range(DE->contents_begin(), DE->contents_end())) {
+    Entries.push_back(From);
     ErrorOr<RedirectingFileSystem::LookupResult> Result =
-        lookupPathImpl(Start, End, DirEntry.get());
+        lookupPathImpl(Start, End, DirEntry.get(), Entries);
     if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
       return Result;
+    Entries.pop_back();
   }
 
   return make_error_code(llvm::errc::no_such_file_or_directory);
 }
 
 static Status getRedirectedFileStatus(const Twine &OriginalPath,
                                       bool UseExternalNames,
                                       Status ExternalStatus) {
if (P && Redirection == RedirectKind::Fallthrough &&
       // Mapped the file but it wasn't found in the underlying filesystem,
       // fallthrough to using the original path if that was the specified
       // redirection type.
       return ExternalFS->getRealPath(CanonicalPath, Output);
     }
     return P;
   }
 
-  // If we found a DirectoryEntry, still fallthrough to the original path if
-  // allowed, because directories don't have a single external contents path.
-  if (Redirection == RedirectKind::Fallthrough)
-    return ExternalFS->getRealPath(CanonicalPath, Output);
+  // We found a DirectoryEntry, which does not have a single external contents
+  // path. Use the canonical virtual path.
+  if (Redirection == RedirectKind::Fallthrough) {
+    Result->getPath(Output);
+    return {};
+  }
   return llvm::errc::invalid_argument;
 }
 
 std::unique_ptr<FileSystem>
 vfs::getVFSFromYAML(std::unique_ptr<MemoryBuffer> Buffer,
                     SourceMgr::DiagHandlerTy DiagHandler,
                     StringRef YAMLFilePath, void *DiagContext,
                     IntrusiveRefCntPtr<FileSystem> ExternalFS) {

llvm/unittests/Support/VirtualFileSystemTest.cpp

 
 TEST_F(VFSFromYAMLTest, GetRealPath) {
   IntrusiveRefCntPtr<DummyFileSystem> Lower(new DummyFileSystem());
   Lower->addDirectory("//dir/");
   Lower->addRegularFile("/foo");
   Lower->addSymlink("/link");
   IntrusiveRefCntPtr<vfs::FileSystem> FS = getFromYAMLString(
       "{ 'use-external-names': false,\n"
+      "  'case-sensitive': false,\n"
       "  'roots': [\n"
       "{\n"
       "  'type': 'directory',\n"
       "  'name': '//root/',\n"
       "  'contents': [ {\n"
       "                  'type': 'file',\n"
       "                  'name': 'bar',\n"
       "                  'external-contents': '/link'\n"
+      "                },\n"
+      "                {\n"
+      "                  'type': 'directory',\n"
+      "                  'name': 'baz',\n"
+      "                  'contents': []\n"
       "                }\n"
       "              ]\n"
       "},\n"
       "{\n"
       "  'type': 'directory',\n"
       "  'name': '//dir/',\n"
       "  'contents': []\n"
       "}\n"
       "]\n"
       "}",
       Lower);
   ASSERT_NE(FS.get(), nullptr);
 
   // Regular file present in underlying file system.
   SmallString<16> RealPath;
   EXPECT_FALSE(FS->getRealPath("/foo", RealPath));
   EXPECT_EQ(RealPath.str(), "/foo");
 
   // File present in YAML pointing to symlink in underlying file system.
   EXPECT_FALSE(FS->getRealPath("//root/bar", RealPath));
   EXPECT_EQ(RealPath.str(), "/symlink");
 
-  // Directories should fall back to the underlying file system is possible.
-  EXPECT_FALSE(FS->getRealPath("//dir/", RealPath));
-  EXPECT_EQ(RealPath.str(), "//dir/");
+  // Directories should return the virtual path as written in the definition.
+  EXPECT_FALSE(FS->getRealPath("//ROOT/baz", RealPath));
+  EXPECT_EQ(RealPath.str(), "//root/baz");
 
   // Try a non-existing file.
   EXPECT_EQ(FS->getRealPath("/non_existing", RealPath),
             errc::no_such_file_or_directory);
 }
 
 TEST_F(VFSFromYAMLTest, WorkingDirectory) {
   IntrusiveRefCntPtr<DummyFileSystem> Lower(new DummyFileSystem());