[VFS] Add a new getVFSFromYAMLs API

[bnbarham]

Summary

Implements redirecting-with using an OverlayFileSystem rather than
nesting RedirectingFileSystem -

• "fallthrough": adds the RedirectingFileSystem to OverlayFileSystem
• "fallback": adds the RedirectingFileSystem *before* the previously added one. This is really only useful when its the initial overlay to place it before the RealFileSystem
• "redirect-only": removes any previously added filesystems. Mostly intended to remove the RealFileSystem, but works in the general case as well.

Updates getVFSFromYAML to use this API, as well as any existing uses
of getVFSFromYAML since it's simpler anyway (ie. no need to read the
underlying buffers first). This does come with a slight change in
semantics though - it is no longer possible to "chain" VFS mappings.
Given an overlay with a mapping of A -> B and another with B -> C, A can
no longer map to C. An A ->C mapping must be specified as its own
mapping if this is desired.

The intention of this change is to allow for simplifying
RedirectingFileSystem by removing all the redirecting-with handling
from it. This will allow reverting it back to its original
implementation where it simply performed the mapping and failed if that
mapping did not exist in ExternalFS. That will be completed in a later
commit to allow for an easier migration path if any downstream user
requires the ability to chain mappings.

Depends on D121423

[bnbarham]

Fixed up the getVFSFromYAML implementation to actually pass the buffer. Note that I'm happy to remove this, I only left it around to make it easier on downstream users.

[bnbarham]

Add a check for CWD when using redirect-only

[bnbarham]

Update to single review dependency

[bnbarham]

Re-order to be before D121424 and merge with D121426

[bnbarham]

There's two failing tests with this change:

• VFSFromYAMLTest.ReturnsExternalPathVFSHit
• VFSFromYAMLTest.ReturnsInternalPathVFSHit

Apparently we allow relative paths in external-contents *without* specifying overlay-relative: true. In this case the relative paths are resolved based on the CWD at the time of the operation. Do we really want that? I believe this wouldn't have worked prior to https://reviews.llvm.org/D109128 as there was no canonicalising before then as well. @keith was that change intentional? If we want it then it will *require* setting CWD on each FS in OverlayFS, which I was really hoping to avoid.

To give the concrete case...

Prior to all these changes:

RedirectingFileSystem
  /a/foo -> bar
ExternalFS
  RealFileSystem
    /a/bar
    /b/bar

cd /a
cat foo # /a/bar

cd /b # fail since it doesn't exist in RedirectingFS

After:

OverlayFileSystem
  RedirectingFileSystem
    /a/foo -> bar

  RealFileSystem
    /a/bar
    /b/bar

cd /a
cat foo # fails since OverlayFS::setCWD doesn't set CWD on the underlying FS

cd /b # succeed
cat foo # fail since there's no /b/foo

In D121424 it will fail for a slightly different reason, but still fail - there's no longer any canonicalise after mapping the path in RedirectingFS (I assumed this was unintentional and missed the test case).

If we want to allow this then I think we'll need to go with the previous plan for OverlayFS, ie. keep track of filesystems that setCWD failed on and don't call them at all until they succeed again. That then doesn't allow certain cases that the current method allows.

[bnbarham]

In D121425#3384188, @bnbarham wrote:

There's two failing tests with this change:

• VFSFromYAMLTest.ReturnsExternalPathVFSHit
• VFSFromYAMLTest.ReturnsInternalPathVFSHit

Apparently we allow relative paths in external-contents *without* specifying overlay-relative: true. In this case the relative paths are resolved based on the CWD at the time of the operation. Do we really want that? I believe this wouldn't have worked prior to https://reviews.llvm.org/D109128 as there was no canonicalising before then as well. @keith was that change intentional? If we want it then it will *require* setting CWD on each FS in OverlayFS, which I was really hoping to avoid.

I spoke to Keith offline. This has always worked - it previously worked by RedirectingFileSystem setting CWD on ExternalFS when setCWD was called on it. It's also important to keep supporting as it's used in Bazel (https://github.com/bazelbuild/rules_swift/blob/c1d7d1df6969c2675c7826ecf1202d78016b1753/swift/internal/vfsoverlay.bzl#L41-L55).

I'm hoping I can fix this by resolving the paths when the overlay is created. I'll see if that works (it'll depend on when -working-directory is actually used by the frontend).

[dexonsmith]

In D121425#3384188, @bnbarham wrote:

There's two failing tests with this change:

• VFSFromYAMLTest.ReturnsExternalPathVFSHit
• VFSFromYAMLTest.ReturnsInternalPathVFSHit

Apparently we allow relative paths in external-contents *without* specifying overlay-relative: true. In this case the relative paths are resolved based on the CWD at the time of the operation. Do we really want that? I believe this wouldn't have worked prior to https://reviews.llvm.org/D109128 as there was no canonicalising before then as well. @keith was that change intentional? If we want it then it will *require* setting CWD on each FS in OverlayFS, which I was really hoping to avoid.

I'm not sure how external-contents factors into this (shouldn't that just affect the observed file path, not whether the lookup succeeds?).

Regardless, here's the testcase again:

OverlayFileSystem
  RedirectingFileSystem
    /a/foo -> bar

  RealFileSystem
    /a/bar
    /b/bar

I think that should behave like:

InMemoryFileSystem
  /a/bar
  /a/foo -> bar (link, with "magic" to sometimes leak path)
  /b/bar

cd /a # succeeds
cat foo # succeeds (get content of /a/bar; report path of /a/bar or /a/foo)

cd /b # succeeds
cat foo # fails

Is the model correct?

If so, I think these are the things we need to get right (not just for that test case):

1. Return error on operations that should fail.
2. Get the right content what cat succeeds.
3. Reporting the "right" paths for files that are opened (depends on external contents, etc.).
4. Keeping the "view" / state consistent when the underlying filesystems changes state.

Does that breakdown make sense?

If so, can you clarify which part is failing? (Not sure if it's (3) or (4)... or maybe some (5).)

Or another way in: I don't fully understand why this fails:

cd /a
cat foo # fails since OverlayFS::setCWD doesn't set CWD on the underlying FS

Can you be more detailed about the overall state at the time of cat, which causes it to fail?

[dexonsmith]

In D121425#3384479, @bnbarham wrote:

In D121425#3384188, @bnbarham wrote:

There's two failing tests with this change:

• VFSFromYAMLTest.ReturnsExternalPathVFSHit
• VFSFromYAMLTest.ReturnsInternalPathVFSHit

Apparently we allow relative paths in external-contents *without* specifying overlay-relative: true. In this case the relative paths are resolved based on the CWD at the time of the operation. Do we really want that? I believe this wouldn't have worked prior to https://reviews.llvm.org/D109128 as there was no canonicalising before then as well. @keith was that change intentional? If we want it then it will *require* setting CWD on each FS in OverlayFS, which I was really hoping to avoid.

I spoke to Keith offline. This has always worked - it previously worked by RedirectingFileSystem setting CWD on ExternalFS when setCWD was called on it. It's also important to keep supporting as it's used in Bazel (https://github.com/bazelbuild/rules_swift/blob/c1d7d1df6969c2675c7826ecf1202d78016b1753/swift/internal/vfsoverlay.bzl#L41-L55).

I'm hoping I can fix this by resolving the paths when the overlay is created. I'll see if that works (it'll depend on when -working-directory is actually used by the frontend).

(Would this mean resolving everything in the .yaml file eagerly at launch? That sounds a bit scary...)

[bnbarham]

In D121425#3384492, @dexonsmith wrote:

Can you be more detailed about the overall state at the time of cat, which causes it to fail?

Sure. I think there's also some confusion with names here but I'm generally trying to use the names as they are used in the overlay YAML or the name of the members in RedirectingFS.

"external-contents" is just the path that we're mapping to, so in my example above (/a/foo -> bar), "bar" is what I was referring to by "external-contents". So let's use that again -

OverlayFileSystem
  RedirectingFileSystem
    /a/foo -> bar

  RealFileSystem
    /a/bar
    /b/bar

After D121423, cd /a will result in the following -

• OverlayFS: CWD set to /a
• RedirectingFS and RealFS: CWD unchanged, so let's assume they were / at the time of creation and that's what they are now

cat foo -

• OverlayFS canonicalises to /a/foo and passes that to openFileForRead in RedirectingFS
• RedirectingFS has a /a/foo -> bar mapping, so it now runs openFileForRead on its ExternalFS (which is the RealFS)
• RealFS is at / and there is no /bar and thus fails
• RedirectingFS also fails
• Back in OverlayFS now, and because we failed we now try RealFS with /a/foo
• RealFS has no /a/foo, it fails
• Back in OverlayFS, all FS have now failed, return a failure

How this used to work really depends on when we're talking about 😆. Prior to D121423 the FS would have looked like:

RedirectingFileSystem
  /a/foo -> bar
ExternalFS
  RealFileSystem
    /a/bar
    /b/bar

Prior to Jonas' change, setCWD on RedirectingFS would run setCWD on ExternalFS. So cd /a would set CWD to /a for both RedirectingFS and RealFileSystem. Then cat /a/foo would give bar and openFileForRead on ExternalFS (RealFS) (which has /a CWD) would open /a/bar.

After Jonas' *and* Keith's change, setCWD no longer runs on ExternalFS but instead the path was canonicalised before sending it along. So /a/foo maps to bar as before, but then it would be canonicalised using RedirectingFS CWD and thus do an open for /a/bar on ExternalFS.

In D121425#3384499, @dexonsmith wrote:

(Would this mean resolving everything in the .yaml file eagerly at launch? That sounds a bit scary...)

Yes, depending on what you mean by "resolving". All I mean is "prefix relative paths with CWD". The main issue with doing this is that it prohibits canonicalising paths to a virtual CWD, since you wouldn't be able to set CWD to a virtual path before making the overlay. Perhaps that's what you mean by "a bit scary" though.

We currently prefix relative paths with ExternalContentsPrefixDir if overlay-relative: true is set. That path is a combination of CWD + the directory to the overlay. This is to handle overlays that have absolute paths that we want to remap (specifically for the crash dump use case I believe). But if overlay-relative: false is set then we just canonicalise the path on open/etc.

I just ran a few tests with the frontend though:

• By default, paths come in relative and will become absolute from the process-wide CWD
• If -working-directory *is* set then paths come in absolute from FileManager - setCWD is never run

I'm not sure if there's a good reason it's done this way or it's just that CWD was only added to FileSystem relatively recently, but it does mean that that we're actually canonicalising the paths with the process-wide CWD regardless at the moment (at least from the frontend). Possibly unexpected since you could pass in -working-directory/foo but the relative mappings would still get canonicalised using the process CWD.

[bnbarham]

Blocked on the dependent

llvm/include/llvm/Support/VirtualFileSystem.h

public:
   std::error_code setCurrentWorkingDirectory(const Twine &Path) override;
 
   void dump(raw_ostream &OS) const override;
 };
 
 /// Get a globally unique ID for a virtual file or directory.
 llvm::sys::fs::UniqueID getNextVirtualUniqueID();
 
-/// Gets a \p FileSystem for a virtual file system described in YAML
-/// format.
+/// \see getVFSFromYAMLs
+///
+/// Returns nullptr if \p Buffer could not be parsed as a YAML containing
+/// overlay mappings.
 std::unique_ptr<FileSystem>
 getVFSFromYAML(std::unique_ptr<llvm::MemoryBuffer> Buffer,
                llvm::SourceMgr::DiagHandlerTy DiagHandler,
                StringRef YAMLFilePath, void *DiagContext = nullptr,
                IntrusiveRefCntPtr<FileSystem> ExternalFS = getRealFileSystem());
 
+/// Convenience function to read each file from \p ExternalFS and pass their
+/// buffers along to the next overload. Returns a \c FileError if any file
+/// could not be read.
+Expected<std::unique_ptr<OverlayFileSystem>>
+getVFSFromYAMLs(ArrayRef<StringRef> YAMLOverlayPaths,
+                IntrusiveRefCntPtr<FileSystem> ExternalFS = getRealFileSystem(),
+                SourceMgr::DiagHandlerTy DiagHandler = nullptr,
+                void *DiagContext = nullptr);
+
+/// Gets a \c FileSystem that runs operations on the virtual filesystems
+/// described by each buffer in \p Buffers and then the \p ExternalFS if those
+/// all fail (dependent on the options below). The order that each is run is
+/// the reverse of the list, ie. the last buffer creates the first used
+/// \c FileSystem.
+///
+/// Returns a \c FileError if any of the buffers are invalid and an
+/// \c OverlayFileSystem with just the \p ExternalFS if no buffers were
+/// provided.
+///
+/// Two extra root configuration options are handled by this method when
+/// parsing the YAML of each filesystem:
+///   'fallthrough': <boolean, default=true, deprecated - use 'redirecting-with'
+///                   instead>
+///   'redirecting-with': <string, one of 'fallthrough', 'fallback', or
+///                        'redirect-only', default='fallthrough'>
+///
+/// These specify the order each filesystem is added to an \c OverlayFileSystem
+/// and whether they're added at all -
+///   - 'fallthrough': allow "falling through" to the next filesystem
+///   - 'fallback': run opertions on the next filesystem before this one.
+///                 Most useful when specified on the first overlay, which
+///                 causes the \p ExternalFS to run before it (ie. "fallback"
+///                 to using the mapped paths only when original fails)
+///   - 'redirect-only': skip running operations on any further filesystems,
+///                      ie. this is the last used filesystem. As with
+///                      'fallback', this is more useful when specified on the
+///                      first overlay to avoid also checking the \p ExternalFS.
+///
+/// \see OverlayFileSystem
+/// \see RedirectingFileSystem
+Expected<std::unique_ptr<OverlayFileSystem>>
+getVFSFromYAMLs(ArrayRef<MemoryBufferRef> YAMLOverlays,
+                IntrusiveRefCntPtr<FileSystem> ExternalFS = getRealFileSystem(),
+                SourceMgr::DiagHandlerTy DiagHandler = nullptr,
+                void *DiagContext = nullptr);
+
 struct YAMLVFSEntry {
   template <typename T1, typename T2>
   YAMLVFSEntry(T1 &&VPath, T2 &&RPath, bool IsDirectory = false)
       : VPath(std::forward<T1>(VPath)), RPath(std::forward<T2>(RPath)),
         IsDirectory(IsDirectory) {}
   std::string VPath;
   std::string RPath;
   bool IsDirectory = false;

 ///
 /// 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, 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> ]
 /// }
ErrorOr<LookupResult> lookupPathImpl(llvm::sys::path::const_iterator Start,
                                        Entry *From) const;
 
 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,
   /// the path it redirects to in the external file system.
   ErrorOr<LookupResult> lookupPath(StringRef CanonicalPath) const;
 
-  /// Parses \p Buffer, which is expected to be in YAML format and
-  /// returns a virtual file system representing its contents.
+  /// Parses \p Buffer, which is expected to be in the YAML format described
+  /// in \c RedirectingFileSystem and returns a virtual file system
+  /// representing its contents.
+  ///
+  /// \see getVFSFromYAMLs
   static std::unique_ptr<RedirectingFileSystem>
   create(std::unique_ptr<MemoryBuffer> Buffer,
          SourceMgr::DiagHandlerTy DiagHandler, StringRef YAMLFilePath,
          void *DiagContext, IntrusiveRefCntPtr<FileSystem> ExternalFS);
 
   /// Redirect each of the remapped files from first to second.
   static std::unique_ptr<RedirectingFileSystem>
   create(ArrayRef<std::pair<std::string, std::string>> RemappedFiles,

llvm/lib/Support/VirtualFileSystem.cpp

RedirectingFileSystem::getRealPath(const Twine &OriginalPath,
   return {};
 }
 
 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,
-                                       YAMLFilePath, DiagContext,
-                                       std::move(ExternalFS));
+  MemoryBufferRef BufferRef {Buffer->getBuffer(), YAMLFilePath};
+  auto FS = getVFSFromYAMLs(BufferRef, ExternalFS, DiagHandler, DiagContext);
+  if (auto Err = FS.takeError()) {
+    consumeError(std::move(Err));
+    return nullptr;
+  }
+  return std::move(*FS);
+}
+
+namespace {
+
+struct VFSResult {
+  IntrusiveRefCntPtr<FileSystem> FS;
+  YAMLParseResult::RedirectKind Redirection;
+
+  VFSResult(IntrusiveRefCntPtr<FileSystem> FS,
+            YAMLParseResult::RedirectKind Redirection)
+      : FS(std::move(FS)), Redirection(Redirection) {}
+
+  VFSResult(YAMLParseResult &Result)
+      : FS(std::move(Result.FS)), Redirection(Result.Redirection) {}
+};
+
+} // namespace
+
+static std::unique_ptr<OverlayFileSystem>
+createOverlay(ArrayRef<VFSResult> VFSResults) {
+  if (VFSResults.empty())
+    return nullptr;
+
+  auto OverlayFS = std::make_unique<OverlayFileSystem>(VFSResults.front().FS);
+  for (const auto &Result : VFSResults.drop_front()) {
+    OverlayFS->pushOverlay(Result.FS);
+  }
+  return OverlayFS;
+}
+
+Expected<std::unique_ptr<OverlayFileSystem>>
+vfs::getVFSFromYAMLs(ArrayRef<StringRef> YAMLOverlayPaths,
+                     IntrusiveRefCntPtr<FileSystem> ExternalFS,
+                     SourceMgr::DiagHandlerTy DiagHandler, void *DiagContext) {
+  SmallVector<MemoryBufferRef, 2> BufferRefs;
+  for (StringRef Path : YAMLOverlayPaths) {
+    BufferRefs.emplace_back(StringRef(), Path);
+  }
+  return getVFSFromYAMLs(BufferRefs, std::move(ExternalFS), DiagHandler,
+                         DiagContext);
+}
+
+Expected<std::unique_ptr<OverlayFileSystem>>
+vfs::getVFSFromYAMLs(ArrayRef<MemoryBufferRef> YAMLOverlays,
+                     IntrusiveRefCntPtr<FileSystem> ExternalFS,
+                     SourceMgr::DiagHandlerTy DiagHandler, void *DiagContext) {
+  if (YAMLOverlays.empty())
+    return std::make_unique<OverlayFileSystem>(std::move(ExternalFS));
+
+  SourceMgr SM;
+  SM.setDiagHandler(DiagHandler, DiagContext);
+
+  SmallVector<VFSResult, 2> Overlays;
+  Overlays.emplace_back(ExternalFS, YAMLParseResult::RedirectKind::Fallthrough);
+  std::unique_ptr<OverlayFileSystem> OverlayFS = createOverlay(Overlays);
+
+  for (MemoryBufferRef Buffer : YAMLOverlays) {
+    // Bit of a hack. If the buffer's data is a nullptr (not just empty),
+    // attempt to read the the file from the current FS. This is to
+    // differentiate between an actual buffer and one that was made from just
+    // a path. The paths cannot be read all up front in order to support
+    // overlay files being defined in a VFS.
+    std::unique_ptr<MemoryBuffer> TempBuffer;
+    if (Buffer.getBuffer().data() == nullptr) {
+      ErrorOr<std::unique_ptr<MemoryBuffer>> NewBufferOrError =
+          OverlayFS->getBufferForFile(Buffer.getBufferIdentifier());
+      if (!NewBufferOrError)
+        return createFileError(Buffer.getBufferIdentifier(),
+                               NewBufferOrError.getError());
+      TempBuffer = std::move(*NewBufferOrError);
+      Buffer = MemoryBufferRef(TempBuffer->getBuffer(),
+                               Buffer.getBufferIdentifier());
+    }
+
+    Optional<YAMLParseResult> Result =
+        RedirectingFileSystemParser::parse(Buffer, SM, ExternalFS);
+    if (!Result)
+      return createFileError(Buffer.getBufferIdentifier(),
+                             llvm::errc::invalid_argument);
+
+    switch (Result->Redirection) {
+    case YAMLParseResult::RedirectKind::Fallthrough:
+      // Simple case - add on the FS
+      Overlays.emplace_back(*Result);
+      OverlayFS->pushOverlay(Overlays.back().FS);
+      break;
+    case YAMLParseResult::RedirectKind::Fallback:
+      // Fallback implies that the previously added FS should run operations
+      // before hitting this FS. This doesn't make a whole lot of sense for any
+      // position other than the beginning where we want the external FS to run
+      // first. For other positions the overlays could just be specified in the
+      // opposite order.
+      //
+      // This is fallout from the history of \c RedirectingFileSystem. Ideally
+      // we would just depend on order and have some way to specify the real
+      // filesystem.
+
+      if (Overlays.back().Redirection !=
+          YAMLParseResult::RedirectKind::RedirectOnly) {
+        // If the previously inserted overlay is redirect only, don't bother
+        // adding this one - it would never run anyway (since redirect only
+        // is necessarily the last FS).
+
+        // Note: Overlays is never empty, it always has at least the
+        // \c ExternalFS
+        Overlays.insert(Overlays.end() - 1, VFSResult(*Result));
+        OverlayFS = createOverlay(Overlays);
+      }
+      break;
+    case YAMLParseResult::RedirectKind::RedirectOnly:
+      // This is now the last FS, clear the rest if there were any
+      Overlays.clear();
+      Overlays.emplace_back(*Result);
+      OverlayFS = createOverlay(Overlays);
+      break;
+    }
+  }
+
+  return OverlayFS;
 }
 
 static void getVFSEntries(RedirectingFileSystem::Entry *SrcE,
                           SmallVectorImpl<StringRef> &Path,
                           SmallVectorImpl<YAMLVFSEntry> &Entries) {
   auto Kind = SrcE->getKind();
   if (Kind == RedirectingFileSystem::EK_Directory) {
     auto *DE = dyn_cast<RedirectingFileSystem::DirectoryEntry>(SrcE);

llvm/unittests/Support/VirtualFileSystemTest.cpp

 //===- unittests/Support/VirtualFileSystem.cpp -------------- VFS tests ---===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/VirtualFileSystem.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/SourceMgr.h"
+#include "llvm/Testing/Support/Error.h"
 #include "llvm/Testing/Support/SupportHelpers.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <map>
 #include <string>
 
 using namespace llvm;
 using llvm::sys::fs::UniqueID;
struct DummyFile : public vfs::File {
   explicit DummyFile(vfs::Status S) : S(S) {}
   llvm::ErrorOr<vfs::Status> status() override { return S; }
   llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
   getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,
             bool IsVolatile) override {
     llvm_unreachable("unimplemented");
   }
   std::error_code close() override { return std::error_code(); }
+  void setPath(const Twine &Path) override { S = S.copyWithNewName(S, Path); }
 };
 
 class DummyFileSystem : public vfs::FileSystem {
   int FSID;   // used to produce UniqueIDs
   int FileID; // used to produce UniqueIDs
   std::string WorkingDirectory;
   std::map<std::string, vfs::Status> FilesAndDirs;
   typedef std::map<std::string, vfs::Status>::const_iterator const_iterator;
TEST_F(VFSFromYAMLTest, RemappedDirectoryOverlayNoFallthrough) {
 
   Lower->addRegularFile("//root/foo/b");
   checkContents(FS->dir_begin("//root/bar", EC),
                 {"//root/foo/a", "//root/foo/b"});
 
   EXPECT_EQ(0, NumDiagnostics);
 }
 
-TEST_F(VFSFromYAMLTest, ReturnsRequestedPathVFSMiss) {
+TEST_F(VFSFromYAMLTest, RelativeVFSPathMiss) {
   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> BaseFS(
       new vfs::InMemoryFileSystem);
   BaseFS->addFile("//root/foo/a", 0,
                   MemoryBuffer::getMemBuffer("contents of a"));
   ASSERT_FALSE(BaseFS->setCurrentWorkingDirectory("//root/foo"));
+
   auto RemappedFS = vfs::RedirectingFileSystem::create(
       {}, /*UseExternalNames=*/false, *BaseFS);
 
-  auto OpenedF = RemappedFS->openFileForRead("a");
+  auto OpenedF = BaseFS->openFileForRead("a");
   ASSERT_FALSE(OpenedF.getError());
-  llvm::ErrorOr<std::string> Name = (*OpenedF)->getName();
-  ASSERT_FALSE(Name.getError());
-  EXPECT_EQ("a", Name.get());
 
-  auto OpenedS = (*OpenedF)->status();
-  ASSERT_FALSE(OpenedS.getError());
-  EXPECT_EQ("a", OpenedS->getName());
-  EXPECT_FALSE(OpenedS->IsVFSMapped);
-
-  auto DirectS = RemappedFS->status("a");
-  ASSERT_FALSE(DirectS.getError());
-  EXPECT_EQ("a", DirectS->getName());
-  EXPECT_FALSE(DirectS->IsVFSMapped);
+  OpenedF = RemappedFS->openFileForRead("a");
+  ASSERT_TRUE(OpenedF.getError());
 
   EXPECT_EQ(0, NumDiagnostics);
 }
 
 TEST_F(VFSFromYAMLTest, ReturnsExternalPathVFSHit) {
   IntrusiveRefCntPtr<vfs::InMemoryFileSystem> BaseFS(
       new vfs::InMemoryFileSystem);
   BaseFS->addFile("//root/foo/realname", 0,
TEST_F(VFSFromYAMLTest, GetRealPath) {
   EXPECT_EQ(RealPath.str(), "//dir/");
 
   // 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());
+  IntrusiveRefCntPtr<ErrorDummyFileSystem> Lower(new ErrorDummyFileSystem());
   Lower->addDirectory("//root/");
   Lower->addDirectory("//root/foo");
   Lower->addRegularFile("//root/foo/a");
   Lower->addRegularFile("//root/foo/b");
   IntrusiveRefCntPtr<vfs::FileSystem> FS = getFromYAMLString(
       "{ 'use-external-names': false,\n"
       "  'roots': [\n"
       "{\n"
       "  'type': 'directory',\n"
       "  'name': '//root/bar',\n"
       "  'contents': [ {\n"
       "                  'type': 'file',\n"
       "                  'name': 'a',\n"
       "                  'external-contents': '//root/foo/a'\n"
       "                }\n"
       "              ]\n"
       "}\n"
       "]\n"
       "}",
       Lower);
   ASSERT_NE(FS.get(), nullptr);
+
   std::error_code EC = FS->setCurrentWorkingDirectory("//root/bar");
   ASSERT_FALSE(EC);
 
   llvm::ErrorOr<std::string> WorkingDir = FS->getCurrentWorkingDirectory();
   ASSERT_TRUE(WorkingDir);
   EXPECT_EQ(*WorkingDir, "//root/bar");
 
   llvm::ErrorOr<vfs::Status> Status = FS->status("./a");
TEST_F(VFSFromYAMLTest, WorkingDirectory) {
   EXPECT_EQ(*WorkingDir, "//root/bar");
 
   EC = FS->setCurrentWorkingDirectory("//root/");
   ASSERT_FALSE(EC);
   WorkingDir = FS->getCurrentWorkingDirectory();
   ASSERT_TRUE(WorkingDir);
   EXPECT_EQ(*WorkingDir, "//root/");
 
+  Status = FS->status("bar/a");
+  ASSERT_FALSE(Status.getError());
+  EXPECT_TRUE(Status->exists());
+
+  // CWD wasn't set on Lower (it just errors instead), so this should fail
+  Status = FS->status("foo/a");
+  ASSERT_TRUE(Status.getError());
+
   EC = FS->setCurrentWorkingDirectory("bar");
   ASSERT_FALSE(EC);
   WorkingDir = FS->getCurrentWorkingDirectory();
   ASSERT_TRUE(WorkingDir);
   EXPECT_EQ(*WorkingDir, "//root/bar");
 }
 
 TEST_F(VFSFromYAMLTest, WorkingDirectoryFallthrough) {
TEST_F(VFSFromYAMLTest, WorkingDirectoryFallthrough) {
   ASSERT_FALSE(Status.getError());
   EXPECT_TRUE(Status->exists());
 
   Status = FS->status("../bar/baz/a");
   ASSERT_FALSE(Status.getError());
   EXPECT_TRUE(Status->exists());
 }
 
-TEST_F(VFSFromYAMLTest, WorkingDirectoryFallthroughInvalid) {
-  IntrusiveRefCntPtr<ErrorDummyFileSystem> Lower(new ErrorDummyFileSystem());
-  Lower->addDirectory("//root/");
-  Lower->addDirectory("//root/foo");
-  Lower->addRegularFile("//root/foo/a");
-  Lower->addRegularFile("//root/foo/b");
-  Lower->addRegularFile("//root/c");
-  IntrusiveRefCntPtr<vfs::FileSystem> FS = getFromYAMLString(
-      "{ 'use-external-names': false,\n"
-      "  'roots': [\n"
-      "{\n"
-      "  'type': 'directory',\n"
-      "  'name': '//root/bar',\n"
-      "  'contents': [ {\n"
-      "                  'type': 'file',\n"
-      "                  'name': 'a',\n"
-      "                  'external-contents': '//root/foo/a'\n"
-      "                }\n"
-      "              ]\n"
-      "}\n"
-      "]\n"
-      "}",
-      Lower);
-  ASSERT_NE(FS.get(), nullptr);
-  std::error_code EC = FS->setCurrentWorkingDirectory("//root/");
-  ASSERT_FALSE(EC);
-  ASSERT_NE(FS.get(), nullptr);
-
-  llvm::ErrorOr<vfs::Status> Status = FS->status("bar/a");
-  ASSERT_FALSE(Status.getError());
-  EXPECT_TRUE(Status->exists());
-
-  Status = FS->status("foo/a");
-  ASSERT_FALSE(Status.getError());
-  EXPECT_TRUE(Status->exists());
-}
-
 TEST_F(VFSFromYAMLTest, VirtualWorkingDirectory) {
   IntrusiveRefCntPtr<ErrorDummyFileSystem> Lower(new ErrorDummyFileSystem());
   Lower->addDirectory("//root/");
   Lower->addDirectory("//root/foo");
   Lower->addRegularFile("//root/foo/a");
   Lower->addRegularFile("//root/foo/b");
   Lower->addRegularFile("//root/c");
   IntrusiveRefCntPtr<vfs::FileSystem> FS = getFromYAMLString(
TEST(RedirectingFileSystemTest, DirectoryStatus) {
   S = FS->status("b");
   ASSERT_FALSE(S.getError());
   EXPECT_EQ("b", S->getName());
 
   S = FS->status("b/c");
   ASSERT_FALSE(S.getError());
   EXPECT_EQ("b/c", S->getName());
 }
+
+static std::unique_ptr<vfs::OverlayFileSystem>
+getVFSOrNull(ArrayRef<std::string> YAMLOverlays,
+             IntrusiveRefCntPtr<vfs::FileSystem> ExternalFS) {
+  SmallVector<MemoryBufferRef> OverlayRefs;
+  for (const auto &Overlay : YAMLOverlays) {
+    OverlayRefs.emplace_back(Overlay, "");
+  }
+
+  auto ExpectedFS = vfs::getVFSFromYAMLs(OverlayRefs, ExternalFS);
+  if (auto Err = ExpectedFS.takeError()) {
+    consumeError(std::move(Err));
+    return nullptr;
+  }
+  return std::move(*ExpectedFS);
+}
+
+static std::string createSimpleOverlay(StringRef RedirectKind, StringRef From,
+                                       StringRef To) {
+  return ("{\n"
+          "  'version': 0,\n"
+          "  'redirecting-with': '" +
+          RedirectKind +
+          "'\n"
+          "  'roots': [\n"
+          "     {\n"
+          "       'type': 'directory-remap',\n"
+          "       'name': '" +
+          From +
+          "',\n"
+          "       'external-contents': '" +
+          To +
+          "',\n"
+          "       }]\n"
+          "     }"
+          "  ]")
+      .str();
+}
+
+// Make sure that overlays are not transitive. Given A -> B and B -> C, if a
+// file in A is requested, it should not end up mapping to C.
+TEST(VFSFromYAMLsTest, NotTransitive) {
+  auto C = makeIntrusiveRefCnt<DummyFileSystem>();
+  C->addDirectory("/real/c");
+  C->addRegularFile("/real/c/f");
+
+  SmallVector<std::string> Overlays;
+  Overlays.push_back(createSimpleOverlay("fallthrough", "/b", "/real/c"));
+  Overlays.push_back(createSimpleOverlay("fallthrough", "/a", "/b"));
+  auto FS = getVFSOrNull(Overlays, C);
+  ASSERT_TRUE(FS);
+
+  auto S = FS->status("/b/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/real/c/f", S->getName());
+
+  S = FS->status("/a/f");
+  EXPECT_TRUE(S.getError());
+}
+
+// When fallback is the first overlay, the external FS should be checked before
+// it. Given B -> A, A should only be used if the file does not exist in B.
+TEST(VFSFromYAMLsTest, FallbackChecksExternalFirst) {
+  auto AOnly = makeIntrusiveRefCnt<DummyFileSystem>();
+  AOnly->addDirectory("/a");
+  AOnly->addRegularFile("/a/f");
+
+  auto BOnly = makeIntrusiveRefCnt<DummyFileSystem>();
+  BOnly->addDirectory("/b");
+  BOnly->addRegularFile("/b/f");
+
+  auto Both = makeIntrusiveRefCnt<DummyFileSystem>();
+  Both->addDirectory("/a");
+  Both->addRegularFile("/a/f");
+  Both->addDirectory("/b");
+  Both->addRegularFile("/b/f");
+
+  auto FallbackOverlay = createSimpleOverlay("fallback", "/b", "/a");
+
+  auto FS = getVFSOrNull(FallbackOverlay, AOnly);
+  ASSERT_TRUE(FS);
+  auto S = FS->status("/b/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/a/f", S->getName());
+
+  FS = getVFSOrNull(FallbackOverlay, BOnly);
+  ASSERT_TRUE(FS);
+  S = FS->status("/b/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/b/f", S->getName());
+
+  FS = getVFSOrNull(FallbackOverlay, Both);
+  ASSERT_TRUE(FS);
+  S = FS->status("/b/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/b/f", S->getName());
+}
+
+// Ensure the last overlay with redirect-only specified is the final FS
+TEST(VFSFromYAMLsTest, RedirectOnlyIsFinalFS) {
+  auto Real = makeIntrusiveRefCnt<DummyFileSystem>();
+  Real->addDirectory("/real");
+  Real->addRegularFile("/real/f");
+  Real->setCurrentWorkingDirectory("/real");
+
+  SmallVector<std::string> Overlays;
+  Overlays.push_back(createSimpleOverlay("redirect-only", "/ro1", "/real"));
+  Overlays.push_back(createSimpleOverlay("fallthrough", "/ft1", "/real"));
+  Overlays.push_back(createSimpleOverlay("redirect-only", "/ro2", "/real"));
+  Overlays.push_back(createSimpleOverlay("fallback", "/fb", "/real"));
+  Overlays.push_back(createSimpleOverlay("fallthrough", "/ft2", "/real"));
+  auto FS = getVFSOrNull(Overlays, Real);
+  ASSERT_TRUE(FS);
+
+  // Should have the same CWD as the external FS we passed down, even if that
+  // FS isn't actually being used in the overlay any more.
+  auto CWD = FS->getCurrentWorkingDirectory();
+  ASSERT_FALSE(CWD.getError());
+  EXPECT_EQ(*CWD, "/real");
+
+  // Only //ft2/f and //ro2/f should be valid:
+  //  - //ro1 and //ft1 are specified before //ro2 so never run
+  //  - //fb is specified after, but it's set to fallback and hence //ro2
+  //    should run first (and not continue)
+
+  auto S = FS->status("/ro1/f");
+  EXPECT_TRUE(S.getError());
+
+  S = FS->status("/ft1/f");
+  EXPECT_TRUE(S.getError());
+
+  S = FS->status("/fb/f");
+  EXPECT_TRUE(S.getError());
+
+  S = FS->status("/ro2/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/real/f", S->getName());
+
+  S = FS->status("/ft2/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/real/f", S->getName());
+}
+
+// Ensure overlays are read from the OverlayFS built so far
+TEST(VFSFromYAMLsTest, OverlayFromVFS) {
+  std::string FT1 = createSimpleOverlay("fallthrough", "/vfs1", "/a");
+  std::string FT2 = createSimpleOverlay("fallthrough", "/vfs2", "/b");
+  std::string FT3 = createSimpleOverlay("fallthrough", "/vfs3", "/c");
+  std::string RO = createSimpleOverlay("redirect-only", "/vfs", "/a");
+
+  auto Real = makeIntrusiveRefCnt<vfs::InMemoryFileSystem>();
+  Real->addFile("/ft1.yaml", 0, MemoryBuffer::getMemBuffer(FT1));
+  Real->addFile("/ft2.yaml", 0, MemoryBuffer::getMemBuffer(FT2));
+  Real->addFile("/a/ft3.yaml", 0, MemoryBuffer::getMemBuffer(FT3));
+  Real->addFile("/ro.yaml", 0, MemoryBuffer::getMemBuffer(RO));
+  Real->addFile("/a/f", 0, MemoryBuffer::getMemBuffer("a"));
+  Real->addFile("/b/f", 0, MemoryBuffer::getMemBuffer("b"));
+  Real->addFile("/c/f", 0, MemoryBuffer::getMemBuffer("c"));
+
+  // 3 to check we're not just using the last overlay
+  auto ExpectedFS =
+      vfs::getVFSFromYAMLs({"/ft1.yaml", "/ft2.yaml", "/vfs1/ft3.yaml"}, Real);
+  ASSERT_THAT_EXPECTED(ExpectedFS, Succeeded());
+  auto FS = std::move(*ExpectedFS);
+  ASSERT_TRUE(FS);
+  auto S = FS->status("/vfs1/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/a/f", S->getName());
+  S = FS->status("/vfs2/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/b/f", S->getName());
+  S = FS->status("/vfs3/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/c/f", S->getName());
+
+  // If redirect-only is given, any further overlays *must* be specified by it
+  ExpectedFS = vfs::getVFSFromYAMLs({"/ro.yaml", "/a/ft3.yaml"}, Real);
+  EXPECT_THAT_EXPECTED(ExpectedFS, Failed());
+
+  ExpectedFS = vfs::getVFSFromYAMLs({"/ro.yaml", "/vfs/ft3.yaml"}, Real);
+  ASSERT_THAT_EXPECTED(ExpectedFS, Succeeded());
+  FS = std::move(*ExpectedFS);
+  ASSERT_TRUE(FS);
+  S = FS->status("/vfs/f");
+  ASSERT_FALSE(S.getError());
+  EXPECT_EQ("/a/f", S->getName());
+}