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

[bnbarham]

Summary

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.

[bnbarham]

Note: I am in no way attached to the name I came up with and would be very open to something better.

[dexonsmith]

Haven't had a chance to look at the code (maybe @keith/@vsapsai/others will have time before I do) but at a high-level this seems pretty sound / SGTM.

The scenario you describe reminds me of the testcase in https://reviews.llvm.org/D117730 ; can you explain if/how this patch relates to that one?

[bnbarham]

In D117937#3268114, @dexonsmith wrote:

The scenario you describe reminds me of the testcase in https://reviews.llvm.org/D117730 ; can you explain if/how this patch relates to that one?

So a "fallback" is what we actually want, ie. there's a folder A that should be used first, falling back to B if the files don't exist. It just so happens that you can "hack" this by providing overlays that I mention in the commit (ie. A -> B and B -> A), but as you mentioned in the other PR it's an "extra layer of complexity" and I'm not sure it was really ever intended to work that way. It also really depends on how the frontend deals with multiple overlays, eg. it used to actually merge them (added them to an OverlayFileSystem instead of just nesting them). In that case you would need to provide A -> A and then A -> B.

Right now, the A -> B and B -> A overlays "hack" to achieve a fallback is broken due to the bug when using multiple overlays (as per the other PR). I think we should fix that bug regardless, but IMO adding a "fallback" makes more sense for what we actually need anyway.

[keith]

I'm definitely not a VFS expert, but I do think this is much nicer than trying to do the other workarounds with multiple VFSs that you described, I left some minor comments, I reviewed carefully but this logic was and is quite dense so I'm heavily relying on the test coverage.

llvm/include/llvm/Support/VirtualFileSystem.h

575

I think redirecting-with is fine, and I can't come up with something better

llvm/lib/Support/VirtualFileSystem.cpp

1341

I know we can only get here if the redirection != redirectOnly, but I think it might be more readable if we had an explicit else if here with fallthrough, and then added an else with an unreachable to make it clear, and make sure if we ever move stuff around we revisit this ordering

1455–1456

Should this case error because the set value was invalid / a typo? Maybe this bubbles up actually?

1870

Should we error in the case that both this key and fallthrough are present? Maybe that's too strict for backwards compat, but right now I guess fallthrough could overwrite this value depending on order?

[bnbarham]

Thanks for taking a look at that @keith, I appreciate it :)! I'll make those changes today hopefully.

llvm/include/llvm/Support/VirtualFileSystem.h

575

Thanks. Do you know if this format is documented anywhere that I would need to update?

llvm/lib/Support/VirtualFileSystem.cpp

1341

Ah yep, I really should have done that in the first place. Thanks!

1455–1456

It ends up returning false down in parse but I need to add a call to error to actually describe the error.

1870

I intentionally allowed both for backwards compatibility, though I'm not sure if that is a real concern after more thinking about it - you'd have to use the new key for it to matter, in which case we don't need to worry about backwards compatibility. So yes, I think we should error if both are present.

I need to add tests for all these error cases as well (both keys present and passing an incorrect value).

[keith]

llvm/include/llvm/Support/VirtualFileSystem.h

575

Folks here used to joke that the source was the documentation, and based on a quick search that still seems to be the case, I don't see any places where the others are mentioned

[bnbarham]

Updated to address Keith's comments. Added an error for an invalid redirect kind as well as when both redirect-with and fallthrough are given. Also added tests for these cases.

[bnbarham]

llvm/include/llvm/Support/VirtualFileSystem.h

575

Not sure if I should be happy that I don't need to update anything or sad that this is the case 😆

[bnbarham]

Failures look unrelated

[bnbarham]

Noticed one of the unit tests wasn't actually testing the right thing.

[bnbarham]

@keith I don't have commit access, would you be able to merge this if you're happy with it?

clang/test/VFS/fallback.c

+// RUN: rm -rf %t
+// RUN: split-file %s %t
+
+// Test fallback directory remapping, ie. a directory "Base" which is used as
+// a fallback if files are missing from "UseFirst"
+
+// RUN: sed -e "s@EXTERNAL_DIR@%{/t:regex_replacement}/Both/Base@g" -e "s@NAME_DIR@%{/t:regex_replacement}/Both/UseFirst@g" %t/vfs/base.yaml > %t/vfs/both.yaml
+
+// RUN: cp -R %t/Both %t/UseFirstOnly
+// RUN: rm -rf %t/UseFirstOnly/Base
+// RUN: sed -e "s@EXTERNAL_DIR@%{/t:regex_replacement}/UseFirstOnly/Base@g" -e "s@NAME_DIR@%{/t:regex_replacement}/UseFirstOnly/UseFirst@g" %t/vfs/base.yaml > %t/vfs/use-first-only.yaml
+
+// RUN: cp -R %t/Both %t/BaseOnly
+// RUN: rm -rf %t/BaseOnly/UseFirst
+// RUN: sed -e "s@EXTERNAL_DIR@%{/t:regex_replacement}/BaseOnly/Base@g" -e "s@NAME_DIR@%{/t:regex_replacement}/BaseOnly/UseFirst@g" %t/vfs/base.yaml > %t/vfs/base-only.yaml
+
+// RUN: cp -R %t/Both %t/BFallback
+// RUN: rm %t/BFallback/UseFirst/B.h
+// RUN: sed -e "s@EXTERNAL_DIR@%{/t:regex_replacement}/BFallback/Base@g" -e "s@NAME_DIR@%{/t:regex_replacement}/BFallback/UseFirst@g" %t/vfs/base.yaml > %t/vfs/b-fallback.yaml
+
+// RUN: cp -R %t/Both %t/CFallback
+// RUN: rm %t/CFallback/UseFirst/C.h
+// RUN: sed -e "s@EXTERNAL_DIR@%{/t:regex_replacement}/CFallback/Base@g" -e "s@NAME_DIR@%{/t:regex_replacement}/CFallback/UseFirst@g" %t/vfs/base.yaml > %t/vfs/c-fallback.yaml
+
+// Both B.h and C.h are in both folders
+// RUN: %clang_cc1 -Werror -I %t/Both/UseFirst -ivfsoverlay %t/vfs/both.yaml -fsyntax-only -E -C %t/main.c 2>&1 | FileCheck --check-prefix=IN_UF %s
+
+// IN_UF: # 1 "{{.*(/|\\\\)UseFirst(/|\\\\)}}B.h"
+// IN_UF-NEXT: // B.h in UseFirst
+// IN_UF: # 1 "{{.*(/|\\\\)UseFirst(/|\\\\)}}C.h"
+// IN_UF-NEXT: // C.h in UseFirst
+
+// Base missing, so now they are only in UseFirst
+// RUN: %clang_cc1 -Werror -I %t/UseFirstOnly/UseFirst -ivfsoverlay %t/vfs/use-first-only.yaml -fsyntax-only -E -C %t/main.c 2>&1 | FileCheck --check-prefix=IN_UF %s
+
+// UseFirst missing, fallback to Base
+// RUN: %clang_cc1 -Werror -I %t/BaseOnly/UseFirst -ivfsoverlay %t/vfs/base-only.yaml -fsyntax-only -E -C %t/main.c 2>&1 | FileCheck --check-prefix=IN_BASE %s
+
+// IN_BASE: # 1 "{{.*(/|\\\\)Base(/|\\\\)}}B.h"
+// IN_BASE-NEXT: // B.h in Base
+// IN_BASE: # 1 "{{.*(/|\\\\)Base(/|\\\\)}}C.h"
+// IN_BASE-NEXT: // C.h in Base
+
+// B.h missing from UseFirst
+// RUN: %clang_cc1 -Werror -I %t/BFallback/UseFirst -ivfsoverlay %t/vfs/b-fallback.yaml -fsyntax-only -E -C %t/main.c 2>&1 | FileCheck --check-prefix=B_FALLBACK %s
+
+// B_FALLBACK: # 1 "{{.*(/|\\\\)Base(/|\\\\)}}B.h"
+// B_FALLBACK-NEXT: // B.h in Base
+// B_FALLBACK: # 1 "{{.*(/|\\\\)UseFirst(/|\\\\)}}C.h"
+// B_FALLBACK-NEXT: // C.h in UseFirst
+
+// C.h missing from UseFirst
+// RUN: %clang_cc1 -Werror -I %t/CFallback/UseFirst -ivfsoverlay %t/vfs/c-fallback.yaml -fsyntax-only -E -C %t/main.c 2>&1 | FileCheck --check-prefix=C_FALLBACK %s
+
+// C_FALLBACK: # 1 "{{.*(/|\\\\)UseFirst(/|\\\\)}}B.h"
+// C_FALLBACK-NEXT: // B.h in UseFirst
+// C_FALLBACK: # 1 "{{.*(/|\\\\)Base(/|\\\\)}}C.h"
+// C_FALLBACK-NEXT: // C.h in Base
+
+//--- main.c
+#include "B.h"
+
+//--- Both/UseFirst/B.h
+// B.h in UseFirst
+#include "C.h"
+
+//--- Both/UseFirst/C.h
+// C.h in UseFirst
+
+//--- Both/Base/B.h
+// B.h in Base
+#include "C.h"
+
+//--- Both/Base/C.h
+// C.h in Base
+
+//--- vfs/base.yaml
+{
+  'version': 0,
+  'redirecting-with': 'fallback',
+  'roots': [
+    { 'name': 'NAME_DIR',
+      'type': 'directory-remap',
+      'external-contents': 'EXTERNAL_DIR'
+    }
+  ]
+}

llvm/include/llvm/Support/VirtualFileSystem.h

 ///
 /// The roots may be absolute or relative. If relative they will be made
 /// absolute against the current working directory.
 ///
 /// All configuration options are optional.
 ///   'case-sensitive': <boolean, default=(true for Posix, false for Windows)>
 ///   'use-external-names': <boolean, default=true>
 ///   'overlay-relative': <boolean, default=false>
-///   'fallthrough': <boolean, default=true>
+///   'fallthrough': <boolean, default=true, deprecated - use 'redirecting-with'
+///                   instead>
+///   'redirecting-with': <string, one of 'fallthrough', 'fallback', or
+///                        'redirect-only', default='fallthrough'>
 ///
 /// Virtual directories that list their contents are represented as
 /// \verbatim
 /// {
 ///   'type': 'directory',
 ///   'name': <string>,
 ///   'contents': [ <file or directory entries> ]
 /// }

 /// FIXME: 'use-external-name' causes behaviour that's inconsistent with how
 /// "real" filesystems behave. Maybe there should be a separate channel for
 /// this information.
 class RedirectingFileSystem : public vfs::FileSystem {
 public:
   enum EntryKind { EK_Directory, EK_DirectoryRemap, EK_File };
   enum NameKind { NK_NotSet, NK_External, NK_Virtual };
 
+  /// The type of redirection to perform.
+  enum class RedirectKind {
+    /// Lookup the redirected path first (ie. the one specified in
+    /// 'external-contents') and if that fails "fallthrough" to a lookup of the
+    /// originally provided path.
+    Fallthrough,
+    /// Lookup the provided path first and if that fails, "fallback" to a
+    /// lookup of the redirected path.
+    Fallback,
+    /// Only lookup the redirected path, do not lookup the originally provided
+    /// path.
+    RedirectOnly
+  };
+
   /// A single file or directory in the VFS.
   class Entry {
     EntryKind Kind;
     std::string Name;
 
   public:
     Entry(EntryKind K, StringRef Name) : Kind(K), Name(Name) {}
     virtual ~Entry() = default;
Optional<StringRef> getExternalRedirect() const {
       return None;
     }
   };
 
 private:
   friend class RedirectingFSDirIterImpl;
   friend class RedirectingFileSystemParser;
 
-  bool shouldUseExternalFS() const { return IsFallthrough; }
-
   /// Canonicalize path by removing ".", "..", "./", components. This is
   /// a VFS request, do not bother about symlinks in the path components
   /// but canonicalize in order to perform the correct entry search.
   std::error_code makeCanonical(SmallVectorImpl<char> &Path) const;
 
-  /// Whether to fall back to the external file system when an operation fails
-  /// with the given error code on a path associated with the provided Entry.
-  bool shouldFallBackToExternalFS(std::error_code EC, Entry *E = nullptr) const;
-
   /// Get the File status, or error, from the underlying external file system.
   /// This returns the status with the originally requested name, while looking
   /// up the entry using the canonical path.
   ErrorOr<Status> getExternalStatus(const Twine &CanonicalPath,
                                     const Twine &OriginalPath) const;
 
   // In a RedirectingFileSystem, keys can be specified in Posix or Windows
   // style (or even a mixture of both), so this comparison helper allows
private:
   /// IsRelativeOverlay marks whether a ExternalContentsPrefixDir path must
   /// be prefixed in every 'external-contents' when reading from YAML files.
   bool IsRelativeOverlay = false;
 
   /// Whether to use to use the value of 'external-contents' for the
   /// names of files.  This global value is overridable on a per-file basis.
   bool UseExternalNames = true;
 
-  /// Whether to attempt a file lookup in external file system after it wasn't
-  /// found in VFS.
-  bool IsFallthrough = true;
+  /// Determines the lookups to perform, as well as their order. See
+  /// \c RedirectKind for details.
+  RedirectKind Redirection = RedirectKind::Fallthrough;
   /// @}
 
   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.
public:
   std::error_code makeAbsolute(SmallVectorImpl<char> &Path) const override;
 
   directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override;
 
   void setExternalContentsPrefixDir(StringRef PrefixDir);
 
   StringRef getExternalContentsPrefixDir() const;
 
-  void setFallthrough(bool Fallthrough);
+  void setRedirection(RedirectingFileSystem::RedirectKind Kind);
 
   std::vector<llvm::StringRef> getRoots() const;
 
   void dump(raw_ostream &OS) const;
   void dumpEntry(raw_ostream &OS, Entry *E, int NumSpaces = 0) const;
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   LLVM_DUMP_METHOD void dump() const;
 #endif

llvm/lib/Support/VirtualFileSystem.cpp

 llvm::vfs::detail::DirIterImpl::~DirIterImpl() = default;
 
 namespace {
 
 /// Combines and deduplicates directory entries across multiple file systems.
 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 {};
   }
 
   std::error_code incrementDirIter(bool IsFirstTime) {
     assert((IsFirstTime || CurrentDirIter != directory_iterator()) &&
            "incrementing past end");
     std::error_code EC;
     if (!IsFirstTime)
       CurrentDirIter.increment(EC);
     if (!EC && CurrentDirIter == directory_iterator())
-      EC = incrementFS();
+      EC = incrementIter(IsFirstTime);
     return EC;
   }
 
   std::error_code incrementImpl(bool IsFirstTime) {
     while (true) {
       std::error_code EC = incrementDirIter(IsFirstTime);
       if (EC || CurrentDirIter == directory_iterator()) {
         CurrentEntry = directory_entry();
         return EC;
       }
       CurrentEntry = *CurrentDirIter;
       StringRef Name = llvm::sys::path::filename(CurrentEntry.path());
       if (SeenNames.insert(Name).second)
         return EC; // name not seen before
     }
     llvm_unreachable("returned above");
   }
 
 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()) {
   }
 
   std::error_code increment() override { return incrementImpl(false); }
 };
 
 } // namespace
 
 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() {}
 
 namespace llvm {
 namespace vfs {
 
 namespace detail {
static llvm::SmallString<256> canonicalize(llvm::StringRef Path) {
   // Now remove the dots.  Explicitly specifying the path style prevents the
   // direction of the slashes from changing.
   llvm::SmallString<256> result =
       llvm::sys::path::remove_leading_dotslash(Path, style);
   llvm::sys::path::remove_dots(result, /*remove_dot_dot=*/true, style);
   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
 
 
 RedirectingFileSystem::RedirectingFileSystem(IntrusiveRefCntPtr<FileSystem> FS)
     : ExternalFS(std::move(FS)) {
   if (ExternalFS)
     if (auto ExternalWorkingDirectory =
             ExternalFS->getCurrentWorkingDirectory()) {
directory_iterator RedirectingFileSystem::dir_begin(const Twine &Dir,
   Dir.toVector(Path);
 
   EC = makeCanonical(Path);
   if (EC)
     return {};
 
   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());
     return {};
   }
 
   // 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;
   }
 
-  if (!shouldUseExternalFS())
-    return DirIter;
-  return directory_iterator(std::make_shared<CombiningDirIterImpl>(
-      DirIter, ExternalFS, std::string(Path), EC));
+  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;
+  if (Redirection == RedirectKind::Fallback) {
+    Iters.push_back(RedirectIter);
+    Iters.push_back(ExternalIter);
+  } else {
+    Iters.push_back(ExternalIter);
+    Iters.push_back(RedirectIter);
+  }
+
+  directory_iterator Combined{
+      std::make_shared<CombiningDirIterImpl>(Iters, EC)};
+  if (EC)
+    return {};
+  return Combined;
 }
 
 void RedirectingFileSystem::setExternalContentsPrefixDir(StringRef PrefixDir) {
   ExternalContentsPrefixDir = PrefixDir.str();
 }
 
 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 {
   std::vector<StringRef> R;
   for (const auto &Root : Roots)
     R.push_back(Root->getName());
   return R;
 }
if (Value.equals_insensitive("true") || Value.equals_insensitive("on") ||
       Result = false;
       return true;
     }
 
     error(N, "expected boolean value");
     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;
 
     KeyStatus(bool Required = false) : Required(Required) {}
   };
 
   using KeyStatusPair = std::pair<StringRef, KeyStatus>;
bool parse(yaml::Node *Root, RedirectingFileSystem *FS) {
     }
 
     KeyStatusPair Fields[] = {
         KeyStatusPair("version", true),
         KeyStatusPair("case-sensitive", false),
         KeyStatusPair("use-external-names", false),
         KeyStatusPair("overlay-relative", false),
         KeyStatusPair("fallthrough", false),
+        KeyStatusPair("redirecting-with", false),
         KeyStatusPair("roots", true),
     };
 
     DenseMap<StringRef, KeyStatus> Keys(std::begin(Fields), std::end(Fields));
     std::vector<std::unique_ptr<RedirectingFileSystem::Entry>> RootEntries;
 
     // Parse configuration and 'roots'
     for (auto &I : *Top) {
for (auto &I : *Top) {
           return false;
       } else if (Key == "overlay-relative") {
         if (!parseScalarBool(I.getValue(), FS->IsRelativeOverlay))
           return false;
       } else if (Key == "use-external-names") {
         if (!parseScalarBool(I.getValue(), FS->UseExternalNames))
           return false;
       } else if (Key == "fallthrough") {
-        if (!parseScalarBool(I.getValue(), FS->IsFallthrough))
+        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 (auto Kind = parseRedirectKind(I.getValue())) {
+          FS->Redirection = *Kind;
+        } else {
+          return false;
+        }
       } else {
         llvm_unreachable("key missing from Keys");
       }
     }
 
     if (Stream.failed())
       return false;
 
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);
   }
 }
 
-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))
     return EC;
 
   llvm::SmallString<256> CanonicalPath =
       canonicalize(StringRef(Path.data(), Path.size()));
   if (CanonicalPath.empty())

 
 ErrorOr<Status> RedirectingFileSystem::status(const Twine &OriginalPath) {
   SmallString<256> CanonicalPath;
   OriginalPath.toVector(CanonicalPath);
 
   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);
   }
 
   return S;
 }
 
 namespace {
 

 ErrorOr<std::unique_ptr<File>>
 RedirectingFileSystem::openFileForRead(const Twine &OriginalPath) {
   SmallString<256> CanonicalPath;
   OriginalPath.toVector(CanonicalPath);
 
   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();
   }
 
   if (!Result->getExternalRedirect()) // FIXME: errc::not_a_file?
     return make_error_code(llvm::errc::invalid_argument);
 
   StringRef ExtRedirect = *Result->getExternalRedirect();
   SmallString<256> CanonicalRemappedPath(ExtRedirect.str());
   if (std::error_code EC = makeCanonical(CanonicalRemappedPath))
     return EC;
 
   auto *RE = cast<RedirectingFileSystem::RemapEntry>(Result->E);
 
   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;
   }
 
   auto ExternalStatus = (*ExternalFile)->status();
   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>(
       std::make_unique<FileWithFixedStatus>(std::move(*ExternalFile), S));
 }
 
 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();
   }
 
   // If we found FileEntry or DirectoryRemapEntry, look up the mapped
   // 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>
 vfs::getVFSFromYAML(std::unique_ptr<MemoryBuffer> Buffer,
                     SourceMgr::DiagHandlerTy DiagHandler,
                     StringRef YAMLFilePath, void *DiagContext,
                     IntrusiveRefCntPtr<FileSystem> ExternalFS) {
   return RedirectingFileSystem::create(std::move(Buffer), DiagHandler,

llvm/unittests/Support/VirtualFileSystemTest.cpp

TEST_F(VFSFromYAMLTest, YAMLVFSWriterTestHandleDirs) {
   IntrusiveRefCntPtr<vfs::FileSystem> FS = getFromYAMLRawString(Buffer, Lower);
   ASSERT_NE(FS.get(), nullptr);
 
   EXPECT_FALSE(FS->exists(_a.path("a")));
   EXPECT_FALSE(FS->exists(_b.path("b")));
   EXPECT_FALSE(FS->exists(_c.path("c")));
 }
 
+TEST_F(VFSFromYAMLTest, RedirectingWith) {
+  IntrusiveRefCntPtr<DummyFileSystem> Both(new DummyFileSystem());
+  Both->addDirectory("//root/a");
+  Both->addRegularFile("//root/a/f");
+  Both->addDirectory("//root/b");
+  Both->addRegularFile("//root/b/f");
+
+  IntrusiveRefCntPtr<DummyFileSystem> AOnly(new DummyFileSystem());
+  AOnly->addDirectory("//root/a");
+  AOnly->addRegularFile("//root/a/f");
+
+  IntrusiveRefCntPtr<DummyFileSystem> BOnly(new DummyFileSystem());
+  BOnly->addDirectory("//root/b");
+  BOnly->addRegularFile("//root/b/f");
+
+  auto BaseStr = std::string("  'roots': [\n"
+                             "    {\n"
+                             "      'type': 'directory-remap',\n"
+                             "      'name': '//root/a',\n"
+                             "      'external-contents': '//root/b'\n"
+                             "    }\n"
+                             "  ]\n"
+                             "}");
+  auto FallthroughStr = "{ 'redirecting-with': 'fallthrough',\n" + BaseStr;
+  auto FallbackStr = "{ 'redirecting-with': 'fallback',\n" + BaseStr;
+  auto RedirectOnlyStr = "{ 'redirecting-with': 'redirect-only',\n" + BaseStr;
+
+  auto ExpectPath = [&](vfs::FileSystem &FS, StringRef Expected,
+                        StringRef Message) {
+    auto AF = FS.openFileForRead("//root/a/f");
+    ASSERT_FALSE(AF.getError()) << Message;
+    auto AFName = (*AF)->getName();
+    ASSERT_FALSE(AFName.getError()) << Message;
+    EXPECT_EQ(Expected.str(), AFName.get()) << Message;
+
+    auto AS = FS.status("//root/a/f");
+    ASSERT_FALSE(AS.getError()) << Message;
+    EXPECT_EQ(Expected.str(), AS->getName()) << Message;
+  };
+
+  auto ExpectFailure = [&](vfs::FileSystem &FS, StringRef Message) {
+    EXPECT_TRUE(FS.openFileForRead("//root/a/f").getError()) << Message;
+    EXPECT_TRUE(FS.status("//root/a/f").getError()) << Message;
+  };
+
+  {
+    // `f` in both `a` and `b`
+
+    // `fallthrough` tries `external-name` first, so should be `b`
+    IntrusiveRefCntPtr<vfs::FileSystem> Fallthrough =
+        getFromYAMLString(FallthroughStr, Both);
+    ASSERT_TRUE(Fallthrough.get() != nullptr);
+    ExpectPath(*Fallthrough, "//root/b/f", "fallthrough, both exist");
+
+    // `fallback` tries the original name first, so should be `a`
+    IntrusiveRefCntPtr<vfs::FileSystem> Fallback =
+        getFromYAMLString(FallbackStr, Both);
+    ASSERT_TRUE(Fallback.get() != nullptr);
+    ExpectPath(*Fallback, "//root/a/f", "fallback, both exist");
+
+    // `redirect-only` is the same as `fallthrough` but doesn't try the
+    // original on failure, so no change here (ie. `b`)
+    IntrusiveRefCntPtr<vfs::FileSystem> Redirect =
+        getFromYAMLString(RedirectOnlyStr, Both);
+    ASSERT_TRUE(Redirect.get() != nullptr);
+    ExpectPath(*Redirect, "//root/b/f", "redirect-only, both exist");
+  }
+
+  {
+    // `f` in `a` only
+
+    // Fallthrough to the original path, `a`
+    IntrusiveRefCntPtr<vfs::FileSystem> Fallthrough =
+        getFromYAMLString(FallthroughStr, AOnly);
+    ASSERT_TRUE(Fallthrough.get() != nullptr);
+    ExpectPath(*Fallthrough, "//root/a/f", "fallthrough, a only");
+
+    // Original first, so still `a`
+    IntrusiveRefCntPtr<vfs::FileSystem> Fallback =
+        getFromYAMLString(FallbackStr, AOnly);
+    ASSERT_TRUE(Fallback.get() != nullptr);
+    ExpectPath(*Fallback, "//root/a/f", "fallback, a only");
+
+    // Fails since no fallthrough
+    IntrusiveRefCntPtr<vfs::FileSystem> Redirect =
+        getFromYAMLString(RedirectOnlyStr, AOnly);
+    ASSERT_TRUE(Redirect.get() != nullptr);
+    ExpectFailure(*Redirect, "redirect-only, a only");
+  }
+
+  {
+    // `f` in `b` only
+
+    // Tries `b` first (no fallthrough)
+    IntrusiveRefCntPtr<vfs::FileSystem> Fallthrough =
+        getFromYAMLString(FallthroughStr, BOnly);
+    ASSERT_TRUE(Fallthrough.get() != nullptr);
+    ExpectPath(*Fallthrough, "//root/b/f", "fallthrough, b only");
+
+    // Tries original first but then fallsback to `b`
+    IntrusiveRefCntPtr<vfs::FileSystem> Fallback =
+        getFromYAMLString(FallbackStr, BOnly);
+    ASSERT_TRUE(Fallback.get() != nullptr);
+    ExpectPath(*Fallback, "//root/b/f", "fallback, b only");
+
+    // Redirect exists, so uses it (`b`)
+    IntrusiveRefCntPtr<vfs::FileSystem> Redirect =
+        getFromYAMLString(RedirectOnlyStr, BOnly);
+    ASSERT_TRUE(Redirect.get() != nullptr);
+    ExpectPath(*Redirect, "//root/b/f", "redirect-only, b only");
+  }
+
+  EXPECT_EQ(0, NumDiagnostics);
+}
+
 TEST(VFSFromRemappedFilesTest, Basic) {
   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> BaseFS =
       new vfs::InMemoryFileSystem;
   BaseFS->addFile("//root/b", 0, MemoryBuffer::getMemBuffer("contents of b"));
   BaseFS->addFile("//root/c", 0, MemoryBuffer::getMemBuffer("contents of c"));
 
   std::vector<std::pair<std::string, std::string>> RemappedFiles = {
       {"//root/a/a", "//root/b"},