[VFS] Add a "redirecting-with" field to overlays

Extend "fallthrough" to allow a third option: "fallback". Fallthrough
allows the original path to used if the redirected (or mapped) path
fails. Fallback is the reverse of this, ie. use the original path and
fallback to the mapped path otherwise.

While this result *can* be achieved today using multiple overlays, this
adds a much more intuitive option. As an example, take two directories
"A" and "B". We would like files from "A" to be used, unless they don't
exist, in which case the VFS should fallback to those in "B".

With the current fallthrough option this is possible by adding two
overlays: one mapping from A -> B and another mapping from B -> A. Since
the frontend *nests* the two RedirectingFileSystems, the result will
be that "A" is mapped to "B" and back to "A", unless it isn't in "A" in
which case it fallsthrough to "B" (or fails if it exists in neither).

Using "fallback" semantics allows a single overlay instead: one mapping
from "A" to "B" but only using that mapping if the operation in "A"
fails first.

"redirect-only" is used to represent the current "fallthrough: false"
case.

Differential Revision: https://reviews.llvm.org/D117937

1 files changed, 215 insertions, 74 deletions

diff --git a/llvm/lib/Support/VirtualFileSystem.cpp b/llvm/lib/Support/VirtualFileSystem.cpp
index f15e301..8573c3a 100644
--- a/llvm/lib/Support/VirtualFileSystem.cpp
+++ b/llvm/lib/Support/VirtualFileSystem.cpp
@@ -467,28 +467,26 @@ namespace {
 class CombiningDirIterImpl : public llvm::vfs::detail::DirIterImpl {
   using FileSystemPtr = llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>;
 
-  /// File systems to check for entries in. Processed in reverse order.
-  SmallVector<FileSystemPtr, 8> FSList;
-  /// The directory iterator for the current filesystem.
+  /// Iterators to combine, processed in reverse order.
+  SmallVector<directory_iterator, 8> IterList;
+  /// The iterator currently being traversed.
   directory_iterator CurrentDirIter;
-  /// The path of the directory to iterate the entries of.
-  std::string DirPath;
   /// The set of names already returned as entries.
   llvm::StringSet<> SeenNames;
 
-  /// Sets \c CurrentDirIter to an iterator of \c DirPath in the next file
-  /// system in the list, or leaves it as is (at its end position) if we've
-  /// already gone through them all.
-  std::error_code incrementFS() {
-    while (!FSList.empty()) {
-      std::error_code EC;
-      CurrentDirIter = FSList.back()->dir_begin(DirPath, EC);
-      FSList.pop_back();
-      if (EC && EC != errc::no_such_file_or_directory)
-        return EC;
+  /// Sets \c CurrentDirIter to the next iterator in the list, or leaves it as
+  /// is (at its end position) if we've already gone through them all.
+  std::error_code incrementIter(bool IsFirstTime) {
+    while (!IterList.empty()) {
+      CurrentDirIter = IterList.back();
+      IterList.pop_back();
       if (CurrentDirIter != directory_iterator())
         break; // found
     }
+
+    if (IsFirstTime && CurrentDirIter == directory_iterator())
+      return std::error_code(static_cast<int>(errc::no_such_file_or_directory),
+                             std::system_category());
     return {};
   }
 
@@ -499,7 +497,7 @@ class CombiningDirIterImpl : public llvm::vfs::detail::DirIterImpl {
     if (!IsFirstTime)
       CurrentDirIter.increment(EC);
     if (!EC && CurrentDirIter == directory_iterator())
-      EC = incrementFS();
+      EC = incrementIter(IsFirstTime);
     return EC;
   }
 
@@ -520,23 +518,24 @@ class CombiningDirIterImpl : public llvm::vfs::detail::DirIterImpl {
 
 public:
   CombiningDirIterImpl(ArrayRef<FileSystemPtr> FileSystems, std::string Dir,
-                       std::error_code &EC)
-      : FSList(FileSystems.begin(), FileSystems.end()),
-        DirPath(std::move(Dir)) {
-    if (!FSList.empty()) {
-      CurrentDirIter = FSList.back()->dir_begin(DirPath, EC);
-      FSList.pop_back();
-      if (!EC || EC == errc::no_such_file_or_directory)
-        EC = incrementImpl(true);
+                       std::error_code &EC) {
+    for (auto FS : FileSystems) {
+      std::error_code FEC;
+      directory_iterator Iter = FS->dir_begin(Dir, FEC);
+      if (FEC && FEC != errc::no_such_file_or_directory) {
+        EC = FEC;
+        return;
+      }
+      if (!FEC)
+        IterList.push_back(Iter);
     }
+    EC = incrementImpl(true);
   }
 
-  CombiningDirIterImpl(directory_iterator FirstIter, FileSystemPtr Fallback,
-                       std::string FallbackDir, std::error_code &EC)
-      : FSList({Fallback}), CurrentDirIter(FirstIter),
-        DirPath(std::move(FallbackDir)) {
-    if (!EC || EC == errc::no_such_file_or_directory)
-      EC = incrementImpl(true);
+  CombiningDirIterImpl(ArrayRef<directory_iterator> DirIters,
+                       std::error_code &EC)
+      : IterList(DirIters.begin(), DirIters.end()) {
+    EC = incrementImpl(true);
   }
 
   std::error_code increment() override { return incrementImpl(false); }
@@ -546,8 +545,11 @@ public:
 
 directory_iterator OverlayFileSystem::dir_begin(const Twine &Dir,
                                                 std::error_code &EC) {
-  return directory_iterator(
+  directory_iterator Combined = directory_iterator(
       std::make_shared<CombiningDirIterImpl>(FSList, Dir.str(), EC));
+  if (EC)
+    return {};
+  return Combined;
 }
 
 void ProxyFileSystem::anchor() {}
@@ -1079,6 +1081,14 @@ static llvm::SmallString<256> canonicalize(llvm::StringRef Path) {
   return result;
 }
 
+/// Whether the error and entry specify a file/directory that was not found.
+static bool isFileNotFound(std::error_code EC,
+                           RedirectingFileSystem::Entry *E = nullptr) {
+  if (E && !isa<RedirectingFileSystem::DirectoryRemapEntry>(E))
+    return false;
+  return EC == llvm::errc::no_such_file_or_directory;
+}
+
 } // anonymous namespace
 
 
@@ -1255,20 +1265,25 @@ directory_iterator RedirectingFileSystem::dir_begin(const Twine &Dir,
 
   ErrorOr<RedirectingFileSystem::LookupResult> Result = lookupPath(Path);
   if (!Result) {
-    EC = Result.getError();
-    if (shouldFallBackToExternalFS(EC))
+    if (Redirection != RedirectKind::RedirectOnly &&
+        isFileNotFound(Result.getError()))
       return ExternalFS->dir_begin(Path, EC);
+
+    EC = Result.getError();
     return {};
   }
 
   // Use status to make sure the path exists and refers to a directory.
   ErrorOr<Status> S = status(Path, Dir, *Result);
   if (!S) {
-    if (shouldFallBackToExternalFS(S.getError(), Result->E))
+    if (Redirection != RedirectKind::RedirectOnly &&
+        isFileNotFound(S.getError(), Result->E))
       return ExternalFS->dir_begin(Dir, EC);
+
     EC = S.getError();
     return {};
   }
+
   if (!S->isDirectory()) {
     EC = std::error_code(static_cast<int>(errc::not_a_directory),
                          std::system_category());
@@ -1277,27 +1292,67 @@ directory_iterator RedirectingFileSystem::dir_begin(const Twine &Dir,
 
   // Create the appropriate directory iterator based on whether we found a
   // DirectoryRemapEntry or DirectoryEntry.
-  directory_iterator DirIter;
+  directory_iterator RedirectIter;
+  std::error_code RedirectEC;
   if (auto ExtRedirect = Result->getExternalRedirect()) {
     auto RE = cast<RedirectingFileSystem::RemapEntry>(Result->E);
-    DirIter = ExternalFS->dir_begin(*ExtRedirect, EC);
+    RedirectIter = ExternalFS->dir_begin(*ExtRedirect, RedirectEC);
 
     if (!RE->useExternalName(UseExternalNames)) {
       // Update the paths in the results to use the virtual directory's path.
-      DirIter =
+      RedirectIter =
           directory_iterator(std::make_shared<RedirectingFSDirRemapIterImpl>(
-              std::string(Path), DirIter));
+              std::string(Path), RedirectIter));
     }
   } else {
     auto DE = cast<DirectoryEntry>(Result->E);
-    DirIter = directory_iterator(std::make_shared<RedirectingFSDirIterImpl>(
-        Path, DE->contents_begin(), DE->contents_end(), EC));
+    RedirectIter =
+        directory_iterator(std::make_shared<RedirectingFSDirIterImpl>(
+            Path, DE->contents_begin(), DE->contents_end(), RedirectEC));
+  }
+
+  if (RedirectEC) {
+    if (RedirectEC != errc::no_such_file_or_directory) {
+      EC = RedirectEC;
+      return {};
+    }
+    RedirectIter = {};
+  }
+
+  if (Redirection == RedirectKind::RedirectOnly) {
+    EC = RedirectEC;
+    return RedirectIter;
+  }
+
+  std::error_code ExternalEC;
+  directory_iterator ExternalIter = ExternalFS->dir_begin(Path, ExternalEC);
+  if (ExternalEC) {
+    if (ExternalEC != errc::no_such_file_or_directory) {
+      EC = ExternalEC;
+      return {};
+    }
+    ExternalIter = {};
+  }
+
+  SmallVector<directory_iterator, 2> Iters;
+  switch (Redirection) {
+  case RedirectKind::Fallthrough:
+    Iters.push_back(ExternalIter);
+    Iters.push_back(RedirectIter);
+    break;
+  case RedirectKind::Fallback:
+    Iters.push_back(RedirectIter);
+    Iters.push_back(ExternalIter);
+    break;
+  default:
+    llvm_unreachable("unhandled RedirectKind");
   }
 
-  if (!shouldUseExternalFS())
-    return DirIter;
-  return directory_iterator(std::make_shared<CombiningDirIterImpl>(
-      DirIter, ExternalFS, std::string(Path), EC));
+  directory_iterator Combined{
+      std::make_shared<CombiningDirIterImpl>(Iters, EC)};
+  if (EC)
+    return {};
+  return Combined;
 }
 
 void RedirectingFileSystem::setExternalContentsPrefixDir(StringRef PrefixDir) {
@@ -1308,8 +1363,9 @@ StringRef RedirectingFileSystem::getExternalContentsPrefixDir() const {
   return ExternalContentsPrefixDir;
 }
 
-void RedirectingFileSystem::setFallthrough(bool Fallthrough) {
-  IsFallthrough = Fallthrough;
+void RedirectingFileSystem::setRedirection(
+    RedirectingFileSystem::RedirectKind Kind) {
+  Redirection = Kind;
 }
 
 std::vector<StringRef> RedirectingFileSystem::getRoots() const {
@@ -1388,6 +1444,23 @@ class llvm::vfs::RedirectingFileSystemParser {
     return false;
   }
 
+  Optional<RedirectingFileSystem::RedirectKind>
+  parseRedirectKind(yaml::Node *N) {
+    SmallString<12> Storage;
+    StringRef Value;
+    if (!parseScalarString(N, Value, Storage))
+      return None;
+
+    if (Value.equals_insensitive("fallthrough")) {
+      return RedirectingFileSystem::RedirectKind::Fallthrough;
+    } else if (Value.equals_insensitive("fallback")) {
+      return RedirectingFileSystem::RedirectKind::Fallback;
+    } else if (Value.equals_insensitive("redirect-only")) {
+      return RedirectingFileSystem::RedirectKind::RedirectOnly;
+    }
+    return None;
+  }
+
   struct KeyStatus {
     bool Required;
     bool Seen = false;
@@ -1731,6 +1804,7 @@ public:
         KeyStatusPair("use-external-names", false),
         KeyStatusPair("overlay-relative", false),
         KeyStatusPair("fallthrough", false),
+        KeyStatusPair("redirecting-with", false),
         KeyStatusPair("roots", true),
     };
 
@@ -1789,8 +1863,34 @@ public:
         if (!parseScalarBool(I.getValue(), FS->UseExternalNames))
           return false;
       } else if (Key == "fallthrough") {
-        if (!parseScalarBool(I.getValue(), FS->IsFallthrough))
+        if (Keys["redirecting-with"].Seen) {
+          error(I.getValue(),
+                "'fallthrough' and 'redirecting-with' are mutually exclusive");
           return false;
+        }
+
+        bool ShouldFallthrough = false;
+        if (!parseScalarBool(I.getValue(), ShouldFallthrough))
+          return false;
+
+        if (ShouldFallthrough) {
+          FS->Redirection = RedirectingFileSystem::RedirectKind::Fallthrough;
+        } else {
+          FS->Redirection = RedirectingFileSystem::RedirectKind::RedirectOnly;
+        }
+      } else if (Key == "redirecting-with") {
+        if (Keys["fallthrough"].Seen) {
+          error(I.getValue(),
+                "'fallthrough' and 'redirecting-with' are mutually exclusive");
+          return false;
+        }
+
+        if (auto Kind = parseRedirectKind(I.getValue())) {
+          FS->Redirection = *Kind;
+        } else {
+          error(I.getValue(), "expected valid redirect kind");
+          return false;
+        }
       } else {
         llvm_unreachable("key missing from Keys");
       }
@@ -1923,13 +2023,6 @@ RedirectingFileSystem::LookupResult::LookupResult(
   }
 }
 
-bool RedirectingFileSystem::shouldFallBackToExternalFS(
-    std::error_code EC, RedirectingFileSystem::Entry *E) const {
-  if (E && !isa<RedirectingFileSystem::DirectoryRemapEntry>(E))
-    return false;
-  return shouldUseExternalFS() && EC == llvm::errc::no_such_file_or_directory;
-}
-
 std::error_code
 RedirectingFileSystem::makeCanonical(SmallVectorImpl<char> &Path) const {
   if (std::error_code EC = makeAbsolute(Path))
@@ -2046,17 +2139,31 @@ ErrorOr<Status> RedirectingFileSystem::status(const Twine &OriginalPath) {
   if (std::error_code EC = makeCanonical(CanonicalPath))
     return EC;
 
+  if (Redirection == RedirectKind::Fallback) {
+    // Attempt to find the original file first, only falling back to the
+    // mapped file if that fails.
+    ErrorOr<Status> S = getExternalStatus(CanonicalPath, OriginalPath);
+    if (S)
+      return S;
+  }
+
   ErrorOr<RedirectingFileSystem::LookupResult> Result =
       lookupPath(CanonicalPath);
   if (!Result) {
-    if (shouldFallBackToExternalFS(Result.getError())) {
+    // Was not able to map file, fallthrough to using the original path if
+    // that was the specified redirection type.
+    if (Redirection == RedirectKind::Fallthrough &&
+        isFileNotFound(Result.getError()))
       return getExternalStatus(CanonicalPath, OriginalPath);
-    }
     return Result.getError();
   }
 
   ErrorOr<Status> S = status(CanonicalPath, OriginalPath, *Result);
-  if (!S && shouldFallBackToExternalFS(S.getError(), Result->E)) {
+  if (!S && Redirection == RedirectKind::Fallthrough &&
+      isFileNotFound(S.getError(), Result->E)) {
+    // 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 getExternalStatus(CanonicalPath, OriginalPath);
   }
 
@@ -2110,13 +2217,24 @@ RedirectingFileSystem::openFileForRead(const Twine &OriginalPath) {
   if (std::error_code EC = makeCanonical(CanonicalPath))
     return EC;
 
+  if (Redirection == RedirectKind::Fallback) {
+    // Attempt to find the original file first, only falling back to the
+    // mapped file if that fails.
+    auto F = File::getWithPath(ExternalFS->openFileForRead(CanonicalPath),
+                               OriginalPath);
+    if (F)
+      return F;
+  }
+
   ErrorOr<RedirectingFileSystem::LookupResult> Result =
       lookupPath(CanonicalPath);
   if (!Result) {
-    if (shouldFallBackToExternalFS(Result.getError()))
+    // Was not able to map file, fallthrough to using the original path if
+    // that was the specified redirection type.
+    if (Redirection == RedirectKind::Fallthrough &&
+        isFileNotFound(Result.getError()))
       return File::getWithPath(ExternalFS->openFileForRead(CanonicalPath),
                                OriginalPath);
-
     return Result.getError();
   }
 
@@ -2133,9 +2251,14 @@ RedirectingFileSystem::openFileForRead(const Twine &OriginalPath) {
   auto ExternalFile = File::getWithPath(
       ExternalFS->openFileForRead(CanonicalRemappedPath), ExtRedirect);
   if (!ExternalFile) {
-    if (shouldFallBackToExternalFS(ExternalFile.getError(), Result->E))
+    if (Redirection == RedirectKind::Fallthrough &&
+        isFileNotFound(ExternalFile.getError(), Result->E)) {
+      // 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 File::getWithPath(ExternalFS->openFileForRead(CanonicalPath),
                                OriginalPath);
+    }
     return ExternalFile;
   }
 
@@ -2143,7 +2266,8 @@ RedirectingFileSystem::openFileForRead(const Twine &OriginalPath) {
   if (!ExternalStatus)
     return ExternalStatus.getError();
 
-  // FIXME: Update the status with the name and VFSMapped.
+  // Otherwise, the file was successfully remapped. Mark it as such. Also
+  // replace the underlying path if the external name is being used.
   Status S = getRedirectedFileStatus(
       OriginalPath, RE->useExternalName(UseExternalNames), *ExternalStatus);
   return std::unique_ptr<File>(
@@ -2151,18 +2275,30 @@ RedirectingFileSystem::openFileForRead(const Twine &OriginalPath) {
 }
 
 std::error_code
-RedirectingFileSystem::getRealPath(const Twine &Path_,
+RedirectingFileSystem::getRealPath(const Twine &OriginalPath,
                                    SmallVectorImpl<char> &Output) const {
-  SmallString<256> Path;
-  Path_.toVector(Path);
+  SmallString<256> CanonicalPath;
+  OriginalPath.toVector(CanonicalPath);
 
-  if (std::error_code EC = makeCanonical(Path))
+  if (std::error_code EC = makeCanonical(CanonicalPath))
     return EC;
 
-  ErrorOr<RedirectingFileSystem::LookupResult> Result = lookupPath(Path);
+  if (Redirection == RedirectKind::Fallback) {
+    // Attempt to find the original file first, only falling back to the
+    // mapped file if that fails.
+    std::error_code EC = ExternalFS->getRealPath(CanonicalPath, Output);
+    if (!EC)
+      return EC;
+  }
+
+  ErrorOr<RedirectingFileSystem::LookupResult> Result =
+      lookupPath(CanonicalPath);
   if (!Result) {
-    if (shouldFallBackToExternalFS(Result.getError()))
-      return ExternalFS->getRealPath(Path, Output);
+    // Was not able to map file, fallthrough to using the original path if
+    // that was the specified redirection type.
+    if (Redirection == RedirectKind::Fallthrough &&
+        isFileNotFound(Result.getError()))
+      return ExternalFS->getRealPath(CanonicalPath, Output);
     return Result.getError();
   }
 
@@ -2170,16 +2306,21 @@ RedirectingFileSystem::getRealPath(const Twine &Path_,
   // path in the external file system.
   if (auto ExtRedirect = Result->getExternalRedirect()) {
     auto P = ExternalFS->getRealPath(*ExtRedirect, Output);
-    if (!P && shouldFallBackToExternalFS(P, Result->E)) {
-      return ExternalFS->getRealPath(Path, Output);
+    if (P && Redirection == RedirectKind::Fallthrough &&
+        isFileNotFound(P, Result->E)) {
+      // 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 fall back to ExternalFS if allowed,
-  // because directories don't have a single external contents path.
-  return shouldUseExternalFS() ? ExternalFS->getRealPath(Path, Output)
-                               : llvm::errc::invalid_argument;
+  // 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);
+  return llvm::errc::invalid_argument;
 }
 
 std::unique_ptr<FileSystem>