1 files changed, 317 insertions, 242 deletions

diff --git a/llvm/lib/Support/VirtualFileSystem.cpp b/llvm/lib/Support/VirtualFileSystem.cpp
index 05332b00bd1f..15bb54e61817 100644
--- a/llvm/lib/Support/VirtualFileSystem.cpp
+++ b/llvm/lib/Support/VirtualFileSystem.cpp
@@ -452,19 +452,27 @@ llvm::vfs::detail::DirIterImpl::~DirIterImpl() = default;
 
 namespace {
 
-class OverlayFSDirIterImpl : public llvm::vfs::detail::DirIterImpl {
-  OverlayFileSystem &Overlays;
-  std::string Path;
-  OverlayFileSystem::iterator CurrentFS;
+/// 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.
   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() {
-    assert(CurrentFS != Overlays.overlays_end() && "incrementing past end");
-    ++CurrentFS;
-    for (auto E = Overlays.overlays_end(); CurrentFS != E; ++CurrentFS) {
+    while (!FSList.empty()) {
       std::error_code EC;
-      CurrentDirIter = (*CurrentFS)->dir_begin(Path, EC);
+      CurrentDirIter = FSList.back()->dir_begin(DirPath, EC);
+      FSList.pop_back();
       if (EC && EC != errc::no_such_file_or_directory)
         return EC;
       if (CurrentDirIter != directory_iterator())
@@ -500,11 +508,24 @@ class OverlayFSDirIterImpl : public llvm::vfs::detail::DirIterImpl {
   }
 
 public:
-  OverlayFSDirIterImpl(const Twine &Path, OverlayFileSystem &FS,
+  CombiningDirIterImpl(ArrayRef<FileSystemPtr> FileSystems, std::string Dir,
                        std::error_code &EC)
-      : Overlays(FS), Path(Path.str()), CurrentFS(Overlays.overlays_begin()) {
-    CurrentDirIter = (*CurrentFS)->dir_begin(Path, EC);
-    EC = incrementImpl(true);
+      : 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);
+    }
+  }
+
+  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);
   }
 
   std::error_code increment() override { return incrementImpl(false); }
@@ -515,7 +536,7 @@ public:
 directory_iterator OverlayFileSystem::dir_begin(const Twine &Dir,
                                                 std::error_code &EC) {
   return directory_iterator(
-      std::make_shared<OverlayFSDirIterImpl>(Dir, *this, EC));
+      std::make_shared<CombiningDirIterImpl>(FSList, Dir.str(), EC));
 }
 
 void ProxyFileSystem::anchor() {}
@@ -990,14 +1011,20 @@ std::error_code InMemoryFileSystem::isLocal(const Twine &Path, bool &Result) {
 
 namespace {
 
-/// Removes leading "./" as well as path components like ".." and ".".
-static llvm::SmallString<256> canonicalize(llvm::StringRef Path) {
-  // First detect the path style in use by checking the first separator.
+static llvm::sys::path::Style getExistingStyle(llvm::StringRef Path) {
+  // Detect the path style in use by checking the first separator.
   llvm::sys::path::Style style = llvm::sys::path::Style::native;
   const size_t n = Path.find_first_of("/\\");
   if (n != static_cast<size_t>(-1))
     style = (Path[n] == '/') ? llvm::sys::path::Style::posix
                              : llvm::sys::path::Style::windows;
+  return style;
+}
+
+/// Removes leading "./" as well as path components like ".." and ".".
+static llvm::SmallString<256> canonicalize(llvm::StringRef Path) {
+  // First detect the path style in use by checking the first separator.
+  llvm::sys::path::Style style = getExistingStyle(Path);
 
   // Now remove the dots.  Explicitly specifying the path style prevents the
   // direction of the slashes from changing.
@@ -1019,48 +1046,88 @@ RedirectingFileSystem::RedirectingFileSystem(IntrusiveRefCntPtr<FileSystem> FS)
     }
 }
 
-// FIXME: reuse implementation common with OverlayFSDirIterImpl as these
-// iterators are conceptually similar.
-class llvm::vfs::VFSFromYamlDirIterImpl
+/// Directory iterator implementation for \c RedirectingFileSystem's
+/// directory entries.
+class llvm::vfs::RedirectingFSDirIterImpl
     : public llvm::vfs::detail::DirIterImpl {
   std::string Dir;
-  RedirectingFileSystem::RedirectingDirectoryEntry::iterator Current, End;
-
-  // To handle 'fallthrough' mode we need to iterate at first through
-  // RedirectingDirectoryEntry and then through ExternalFS. These operations are
-  // done sequentially, we just need to keep a track of what kind of iteration
-  // we are currently performing.
-
-  /// Flag telling if we should iterate through ExternalFS or stop at the last
-  /// RedirectingDirectoryEntry::iterator.
-  bool IterateExternalFS;
-  /// Flag telling if we have switched to iterating through ExternalFS.
-  bool IsExternalFSCurrent = false;
-  FileSystem &ExternalFS;
-  directory_iterator ExternalDirIter;
-  llvm::StringSet<> SeenNames;
+  RedirectingFileSystem::DirectoryEntry::iterator Current, End;
+
+  std::error_code incrementImpl(bool IsFirstTime) {
+    assert((IsFirstTime || Current != End) && "cannot iterate past end");
+    if (!IsFirstTime)
+      ++Current;
+    if (Current != End) {
+      SmallString<128> PathStr(Dir);
+      llvm::sys::path::append(PathStr, (*Current)->getName());
+      sys::fs::file_type Type = sys::fs::file_type::type_unknown;
+      switch ((*Current)->getKind()) {
+      case RedirectingFileSystem::EK_Directory:
+        LLVM_FALLTHROUGH;
+      case RedirectingFileSystem::EK_DirectoryRemap:
+        Type = sys::fs::file_type::directory_file;
+        break;
+      case RedirectingFileSystem::EK_File:
+        Type = sys::fs::file_type::regular_file;
+        break;
+      }
+      CurrentEntry = directory_entry(std::string(PathStr.str()), Type);
+    } else {
+      CurrentEntry = directory_entry();
+    }
+    return {};
+  };
+
+public:
+  RedirectingFSDirIterImpl(
+      const Twine &Path, RedirectingFileSystem::DirectoryEntry::iterator Begin,
+      RedirectingFileSystem::DirectoryEntry::iterator End, std::error_code &EC)
+      : Dir(Path.str()), Current(Begin), End(End) {
+    EC = incrementImpl(/*IsFirstTime=*/true);
+  }
 
-  /// To combine multiple iterations, different methods are responsible for
-  /// different iteration steps.
-  /// @{
+  std::error_code increment() override {
+    return incrementImpl(/*IsFirstTime=*/false);
+  }
+};
 
-  /// Responsible for dispatching between RedirectingDirectoryEntry iteration
-  /// and ExternalFS iteration.
-  std::error_code incrementImpl(bool IsFirstTime);
-  /// Responsible for RedirectingDirectoryEntry iteration.
-  std::error_code incrementContent(bool IsFirstTime);
-  /// Responsible for ExternalFS iteration.
-  std::error_code incrementExternal();
-  /// @}
+/// Directory iterator implementation for \c RedirectingFileSystem's
+/// directory remap entries that maps the paths reported by the external
+/// file system's directory iterator back to the virtual directory's path.
+class RedirectingFSDirRemapIterImpl : public llvm::vfs::detail::DirIterImpl {
+  std::string Dir;
+  llvm::sys::path::Style DirStyle;
+  llvm::vfs::directory_iterator ExternalIter;
 
 public:
-  VFSFromYamlDirIterImpl(
-      const Twine &Path,
-      RedirectingFileSystem::RedirectingDirectoryEntry::iterator Begin,
-      RedirectingFileSystem::RedirectingDirectoryEntry::iterator End,
-      bool IterateExternalFS, FileSystem &ExternalFS, std::error_code &EC);
+  RedirectingFSDirRemapIterImpl(std::string DirPath,
+                                llvm::vfs::directory_iterator ExtIter)
+      : Dir(std::move(DirPath)), DirStyle(getExistingStyle(Dir)),
+        ExternalIter(ExtIter) {
+    if (ExternalIter != llvm::vfs::directory_iterator())
+      setCurrentEntry();
+  }
+
+  void setCurrentEntry() {
+    StringRef ExternalPath = ExternalIter->path();
+    llvm::sys::path::Style ExternalStyle = getExistingStyle(ExternalPath);
+    StringRef File = llvm::sys::path::filename(ExternalPath, ExternalStyle);
 
-  std::error_code increment() override;
+    SmallString<128> NewPath(Dir);
+    llvm::sys::path::append(NewPath, DirStyle, File);
+
+    CurrentEntry = directory_entry(std::string(NewPath), ExternalIter->type());
+  }
+
+  std::error_code increment() override {
+    std::error_code EC;
+    ExternalIter.increment(EC);
+    if (!EC && ExternalIter != llvm::vfs::directory_iterator())
+      setCurrentEntry();
+    else
+      CurrentEntry = directory_entry();
+    return EC;
+  }
 };
 
 llvm::ErrorOr<std::string>
@@ -1131,15 +1198,19 @@ directory_iterator RedirectingFileSystem::dir_begin(const Twine &Dir,
   if (EC)
     return {};
 
-  ErrorOr<RedirectingFileSystem::Entry *> E = lookupPath(Path);
-  if (!E) {
-    EC = E.getError();
-    if (shouldUseExternalFS() && EC == errc::no_such_file_or_directory)
+  ErrorOr<RedirectingFileSystem::LookupResult> Result = lookupPath(Path);
+  if (!Result) {
+    EC = Result.getError();
+    if (shouldFallBackToExternalFS(EC))
       return ExternalFS->dir_begin(Path, EC);
     return {};
   }
-  ErrorOr<Status> S = status(Path, *E);
+
+  // Use status to make sure the path exists and refers to a directory.
+  ErrorOr<Status> S = status(Path, *Result);
   if (!S) {
+    if (shouldFallBackToExternalFS(S.getError(), Result->E))
+      return ExternalFS->dir_begin(Dir, EC);
     EC = S.getError();
     return {};
   }
@@ -1149,10 +1220,29 @@ directory_iterator RedirectingFileSystem::dir_begin(const Twine &Dir,
     return {};
   }
 
-  auto *D = cast<RedirectingFileSystem::RedirectingDirectoryEntry>(*E);
-  return directory_iterator(std::make_shared<VFSFromYamlDirIterImpl>(
-      Path, D->contents_begin(), D->contents_end(),
-      /*IterateExternalFS=*/shouldUseExternalFS(), *ExternalFS, EC));
+  // Create the appropriate directory iterator based on whether we found a
+  // DirectoryRemapEntry or DirectoryEntry.
+  directory_iterator DirIter;
+  if (auto ExtRedirect = Result->getExternalRedirect()) {
+    auto RE = cast<RedirectingFileSystem::RemapEntry>(Result->E);
+    DirIter = ExternalFS->dir_begin(*ExtRedirect, EC);
+
+    if (!RE->useExternalName(UseExternalNames)) {
+      // Update the paths in the results to use the virtual directory's path.
+      DirIter =
+          directory_iterator(std::make_shared<RedirectingFSDirRemapIterImpl>(
+              std::string(Path), DirIter));
+    }
+  } else {
+    auto DE = cast<DirectoryEntry>(Result->E);
+    DirIter = directory_iterator(std::make_shared<RedirectingFSDirIterImpl>(
+        Path, DE->contents_begin(), DE->contents_end(), EC));
+  }
+
+  if (!shouldUseExternalFS())
+    return DirIter;
+  return directory_iterator(std::make_shared<CombiningDirIterImpl>(
+      DirIter, ExternalFS, std::string(Path), EC));
 }
 
 void RedirectingFileSystem::setExternalContentsPrefixDir(StringRef PrefixDir) {
@@ -1189,7 +1279,7 @@ void RedirectingFileSystem::dumpEntry(raw_ostream &OS,
      << "\n";
 
   if (E->getKind() == RedirectingFileSystem::EK_Directory) {
-    auto *DE = dyn_cast<RedirectingFileSystem::RedirectingDirectoryEntry>(E);
+    auto *DE = dyn_cast<RedirectingFileSystem::DirectoryEntry>(E);
     assert(DE && "Should be a directory");
 
     for (std::unique_ptr<Entry> &SubEntry :
@@ -1228,12 +1318,13 @@ class llvm::vfs::RedirectingFileSystemParser {
     if (!parseScalarString(N, Value, Storage))
       return false;
 
-    if (Value.equals_lower("true") || Value.equals_lower("on") ||
-        Value.equals_lower("yes") || Value == "1") {
+    if (Value.equals_insensitive("true") || Value.equals_insensitive("on") ||
+        Value.equals_insensitive("yes") || Value == "1") {
       Result = true;
       return true;
-    } else if (Value.equals_lower("false") || Value.equals_lower("off") ||
-               Value.equals_lower("no") || Value == "0") {
+    } else if (Value.equals_insensitive("false") ||
+               Value.equals_insensitive("off") ||
+               Value.equals_insensitive("no") || Value == "0") {
       Result = false;
       return true;
     }
@@ -1290,13 +1381,11 @@ public:
         }
       }
     } else { // Advance to the next component
-      auto *DE = dyn_cast<RedirectingFileSystem::RedirectingDirectoryEntry>(
-          ParentEntry);
+      auto *DE = dyn_cast<RedirectingFileSystem::DirectoryEntry>(ParentEntry);
       for (std::unique_ptr<RedirectingFileSystem::Entry> &Content :
            llvm::make_range(DE->contents_begin(), DE->contents_end())) {
         auto *DirContent =
-            dyn_cast<RedirectingFileSystem::RedirectingDirectoryEntry>(
-                Content.get());
+            dyn_cast<RedirectingFileSystem::DirectoryEntry>(Content.get());
         if (DirContent && Name.equals(Content->getName()))
           return DirContent;
       }
@@ -1304,7 +1393,7 @@ public:
 
     // ... or create a new one
     std::unique_ptr<RedirectingFileSystem::Entry> E =
-        std::make_unique<RedirectingFileSystem::RedirectingDirectoryEntry>(
+        std::make_unique<RedirectingFileSystem::DirectoryEntry>(
             Name, Status("", getNextVirtualUniqueID(),
                          std::chrono::system_clock::now(), 0, 0, 0,
                          file_type::directory_file, sys::fs::all_all));
@@ -1315,8 +1404,7 @@ public:
       return ParentEntry;
     }
 
-    auto *DE =
-        cast<RedirectingFileSystem::RedirectingDirectoryEntry>(ParentEntry);
+    auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(ParentEntry);
     DE->addContent(std::move(E));
     return DE->getLastContent();
   }
@@ -1328,7 +1416,7 @@ private:
     StringRef Name = SrcE->getName();
     switch (SrcE->getKind()) {
     case RedirectingFileSystem::EK_Directory: {
-      auto *DE = cast<RedirectingFileSystem::RedirectingDirectoryEntry>(SrcE);
+      auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(SrcE);
       // Empty directories could be present in the YAML as a way to
       // describe a file for a current directory after some of its subdir
       // is parsed. This only leads to redundant walks, ignore it.
@@ -1339,14 +1427,21 @@ private:
         uniqueOverlayTree(FS, SubEntry.get(), NewParentE);
       break;
     }
-    case RedirectingFileSystem::EK_File: {
+    case RedirectingFileSystem::EK_DirectoryRemap: {
       assert(NewParentE && "Parent entry must exist");
-      auto *FE = cast<RedirectingFileSystem::RedirectingFileEntry>(SrcE);
-      auto *DE =
-          cast<RedirectingFileSystem::RedirectingDirectoryEntry>(NewParentE);
+      auto *DR = cast<RedirectingFileSystem::DirectoryRemapEntry>(SrcE);
+      auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(NewParentE);
       DE->addContent(
-          std::make_unique<RedirectingFileSystem::RedirectingFileEntry>(
-              Name, FE->getExternalContentsPath(), FE->getUseName()));
+          std::make_unique<RedirectingFileSystem::DirectoryRemapEntry>(
+              Name, DR->getExternalContentsPath(), DR->getUseName()));
+      break;
+    }
+    case RedirectingFileSystem::EK_File: {
+      assert(NewParentE && "Parent entry must exist");
+      auto *FE = cast<RedirectingFileSystem::FileEntry>(SrcE);
+      auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(NewParentE);
+      DE->addContent(std::make_unique<RedirectingFileSystem::FileEntry>(
+          Name, FE->getExternalContentsPath(), FE->getUseName()));
       break;
     }
     }
@@ -1370,14 +1465,13 @@ private:
 
     DenseMap<StringRef, KeyStatus> Keys(std::begin(Fields), std::end(Fields));
 
-    bool HasContents = false; // external or otherwise
+    enum { CF_NotSet, CF_List, CF_External } ContentsField = CF_NotSet;
     std::vector<std::unique_ptr<RedirectingFileSystem::Entry>>
         EntryArrayContents;
     SmallString<256> ExternalContentsPath;
     SmallString<256> Name;
     yaml::Node *NameValueNode = nullptr;
-    auto UseExternalName =
-        RedirectingFileSystem::RedirectingFileEntry::NK_NotSet;
+    auto UseExternalName = RedirectingFileSystem::NK_NotSet;
     RedirectingFileSystem::EntryKind Kind;
 
     for (auto &I : *M) {
@@ -1407,17 +1501,19 @@ private:
           Kind = RedirectingFileSystem::EK_File;
         else if (Value == "directory")
           Kind = RedirectingFileSystem::EK_Directory;
+        else if (Value == "directory-remap")
+          Kind = RedirectingFileSystem::EK_DirectoryRemap;
         else {
           error(I.getValue(), "unknown value for 'type'");
           return nullptr;
         }
       } else if (Key == "contents") {
-        if (HasContents) {
+        if (ContentsField != CF_NotSet) {
           error(I.getKey(),
                 "entry already has 'contents' or 'external-contents'");
           return nullptr;
         }
-        HasContents = true;
+        ContentsField = CF_List;
         auto *Contents = dyn_cast<yaml::SequenceNode>(I.getValue());
         if (!Contents) {
           // FIXME: this is only for directories, what about files?
@@ -1433,12 +1529,12 @@ private:
             return nullptr;
         }
       } else if (Key == "external-contents") {
-        if (HasContents) {
+        if (ContentsField != CF_NotSet) {
           error(I.getKey(),
                 "entry already has 'contents' or 'external-contents'");
           return nullptr;
         }
-        HasContents = true;
+        ContentsField = CF_External;
         if (!parseScalarString(I.getValue(), Value, Buffer))
           return nullptr;
 
@@ -1460,9 +1556,8 @@ private:
         bool Val;
         if (!parseScalarBool(I.getValue(), Val))
           return nullptr;
-        UseExternalName =
-            Val ? RedirectingFileSystem::RedirectingFileEntry::NK_External
-                : RedirectingFileSystem::RedirectingFileEntry::NK_Virtual;
+        UseExternalName = Val ? RedirectingFileSystem::NK_External
+                              : RedirectingFileSystem::NK_Virtual;
       } else {
         llvm_unreachable("key missing from Keys");
       }
@@ -1472,7 +1567,7 @@ private:
       return nullptr;
 
     // check for missing keys
-    if (!HasContents) {
+    if (ContentsField == CF_NotSet) {
       error(N, "missing key 'contents' or 'external-contents'");
       return nullptr;
     }
@@ -1481,9 +1576,14 @@ private:
 
     // check invalid configuration
     if (Kind == RedirectingFileSystem::EK_Directory &&
-        UseExternalName !=
-            RedirectingFileSystem::RedirectingFileEntry::NK_NotSet) {
-      error(N, "'use-external-name' is not supported for directories");
+        UseExternalName != RedirectingFileSystem::NK_NotSet) {
+      error(N, "'use-external-name' is not supported for 'directory' entries");
+      return nullptr;
+    }
+
+    if (Kind == RedirectingFileSystem::EK_DirectoryRemap &&
+        ContentsField == CF_List) {
+      error(N, "'contents' is not supported for 'directory-remap' entries");
       return nullptr;
     }
 
@@ -1504,7 +1604,7 @@ private:
     }
 
     // Remove trailing slash(es), being careful not to remove the root path
-    StringRef Trimmed(Name);
+    StringRef Trimmed = Name;
     size_t RootPathLen = sys::path::root_path(Trimmed, path_style).size();
     while (Trimmed.size() > RootPathLen &&
            sys::path::is_separator(Trimmed.back(), path_style))
@@ -1516,16 +1616,18 @@ private:
     std::unique_ptr<RedirectingFileSystem::Entry> Result;
     switch (Kind) {
     case RedirectingFileSystem::EK_File:
-      Result = std::make_unique<RedirectingFileSystem::RedirectingFileEntry>(
+      Result = std::make_unique<RedirectingFileSystem::FileEntry>(
+          LastComponent, std::move(ExternalContentsPath), UseExternalName);
+      break;
+    case RedirectingFileSystem::EK_DirectoryRemap:
+      Result = std::make_unique<RedirectingFileSystem::DirectoryRemapEntry>(
           LastComponent, std::move(ExternalContentsPath), UseExternalName);
       break;
     case RedirectingFileSystem::EK_Directory:
-      Result =
-          std::make_unique<RedirectingFileSystem::RedirectingDirectoryEntry>(
-              LastComponent, std::move(EntryArrayContents),
-              Status("", getNextVirtualUniqueID(),
-                     std::chrono::system_clock::now(), 0, 0, 0,
-                     file_type::directory_file, sys::fs::all_all));
+      Result = std::make_unique<RedirectingFileSystem::DirectoryEntry>(
+          LastComponent, std::move(EntryArrayContents),
+          Status("", getNextVirtualUniqueID(), std::chrono::system_clock::now(),
+                 0, 0, 0, file_type::directory_file, sys::fs::all_all));
       break;
     }
 
@@ -1539,12 +1641,10 @@ private:
          I != E; ++I) {
       std::vector<std::unique_ptr<RedirectingFileSystem::Entry>> Entries;
       Entries.push_back(std::move(Result));
-      Result =
-          std::make_unique<RedirectingFileSystem::RedirectingDirectoryEntry>(
-              *I, std::move(Entries),
-              Status("", getNextVirtualUniqueID(),
-                     std::chrono::system_clock::now(), 0, 0, 0,
-                     file_type::directory_file, sys::fs::all_all));
+      Result = std::make_unique<RedirectingFileSystem::DirectoryEntry>(
+          *I, std::move(Entries),
+          Status("", getNextVirtualUniqueID(), std::chrono::system_clock::now(),
+                 0, 0, 0, file_type::directory_file, sys::fs::all_all));
     }
     return Result;
   }
@@ -1731,20 +1831,40 @@ std::unique_ptr<RedirectingFileSystem> RedirectingFileSystem::create(
     }
 
     // Add the file.
-    auto NewFile =
-        std::make_unique<RedirectingFileSystem::RedirectingFileEntry>(
-            llvm::sys::path::filename(From), To,
-            UseExternalNames
-                ? RedirectingFileSystem::RedirectingFileEntry::NK_External
-                : RedirectingFileSystem::RedirectingFileEntry::NK_Virtual);
+    auto NewFile = std::make_unique<RedirectingFileSystem::FileEntry>(
+        llvm::sys::path::filename(From), To,
+        UseExternalNames ? RedirectingFileSystem::NK_External
+                         : RedirectingFileSystem::NK_Virtual);
     ToEntry = NewFile.get();
-    cast<RedirectingFileSystem::RedirectingDirectoryEntry>(Parent)->addContent(
+    cast<RedirectingFileSystem::DirectoryEntry>(Parent)->addContent(
         std::move(NewFile));
   }
 
   return FS;
 }
 
+RedirectingFileSystem::LookupResult::LookupResult(
+    Entry *E, sys::path::const_iterator Start, sys::path::const_iterator End)
+    : E(E) {
+  assert(E != nullptr);
+  // If the matched entry is a DirectoryRemapEntry, set ExternalRedirect to the
+  // path of the directory it maps to in the external file system plus any
+  // remaining path components in the provided iterator.
+  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))
@@ -1759,23 +1879,23 @@ RedirectingFileSystem::makeCanonical(SmallVectorImpl<char> &Path) const {
   return {};
 }
 
-ErrorOr<RedirectingFileSystem::Entry *>
+ErrorOr<RedirectingFileSystem::LookupResult>
 RedirectingFileSystem::lookupPath(StringRef Path) const {
   sys::path::const_iterator Start = sys::path::begin(Path);
   sys::path::const_iterator End = sys::path::end(Path);
   for (const auto &Root : Roots) {
-    ErrorOr<RedirectingFileSystem::Entry *> Result =
-        lookupPath(Start, End, Root.get());
+    ErrorOr<RedirectingFileSystem::LookupResult> Result =
+        lookupPathImpl(Start, End, Root.get());
     if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
       return Result;
   }
   return make_error_code(llvm::errc::no_such_file_or_directory);
 }
 
-ErrorOr<RedirectingFileSystem::Entry *>
-RedirectingFileSystem::lookupPath(sys::path::const_iterator Start,
-                                  sys::path::const_iterator End,
-                                  RedirectingFileSystem::Entry *From) const {
+ErrorOr<RedirectingFileSystem::LookupResult>
+RedirectingFileSystem::lookupPathImpl(
+    sys::path::const_iterator Start, sys::path::const_iterator End,
+    RedirectingFileSystem::Entry *From) const {
   assert(!isTraversalComponent(*Start) &&
          !isTraversalComponent(From->getName()) &&
          "Paths should not contain traversal components");
@@ -1791,18 +1911,21 @@ RedirectingFileSystem::lookupPath(sys::path::const_iterator Start,
 
     if (Start == End) {
       // Match!
-      return From;
+      return LookupResult(From, Start, End);
     }
   }
 
-  auto *DE = dyn_cast<RedirectingFileSystem::RedirectingDirectoryEntry>(From);
-  if (!DE)
+  if (isa<RedirectingFileSystem::FileEntry>(From))
     return make_error_code(llvm::errc::not_a_directory);
 
+  if (isa<RedirectingFileSystem::DirectoryRemapEntry>(From))
+    return LookupResult(From, Start, End);
+
+  auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(From);
   for (const std::unique_ptr<RedirectingFileSystem::Entry> &DirEntry :
        llvm::make_range(DE->contents_begin(), DE->contents_end())) {
-    ErrorOr<RedirectingFileSystem::Entry *> Result =
-        lookupPath(Start, End, DirEntry.get());
+    ErrorOr<RedirectingFileSystem::LookupResult> Result =
+        lookupPathImpl(Start, End, DirEntry.get());
     if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
       return Result;
   }
@@ -1819,20 +1942,19 @@ static Status getRedirectedFileStatus(const Twine &Path, bool UseExternalNames,
   return S;
 }
 
-ErrorOr<Status> RedirectingFileSystem::status(const Twine &Path,
-                                              RedirectingFileSystem::Entry *E) {
-  assert(E != nullptr);
-  if (auto *F = dyn_cast<RedirectingFileSystem::RedirectingFileEntry>(E)) {
-    ErrorOr<Status> S = ExternalFS->status(F->getExternalContentsPath());
-    assert(!S || S->getName() == F->getExternalContentsPath());
-    if (S)
-      return getRedirectedFileStatus(Path, F->useExternalName(UseExternalNames),
-                                     *S);
-    return S;
-  } else { // directory
-    auto *DE = cast<RedirectingFileSystem::RedirectingDirectoryEntry>(E);
-    return Status::copyWithNewName(DE->getStatus(), Path);
+ErrorOr<Status> RedirectingFileSystem::status(
+    const Twine &Path, const RedirectingFileSystem::LookupResult &Result) {
+  if (Optional<StringRef> ExtRedirect = Result.getExternalRedirect()) {
+    ErrorOr<Status> S = ExternalFS->status(*ExtRedirect);
+    if (!S)
+      return S;
+    auto *RE = cast<RedirectingFileSystem::RemapEntry>(Result.E);
+    return getRedirectedFileStatus(Path, RE->useExternalName(UseExternalNames),
+                                   *S);
   }
+
+  auto *DE = cast<RedirectingFileSystem::DirectoryEntry>(Result.E);
+  return Status::copyWithNewName(DE->getStatus(), Path);
 }
 
 ErrorOr<Status> RedirectingFileSystem::status(const Twine &Path_) {
@@ -1842,15 +1964,17 @@ ErrorOr<Status> RedirectingFileSystem::status(const Twine &Path_) {
   if (std::error_code EC = makeCanonical(Path))
     return EC;
 
-  ErrorOr<RedirectingFileSystem::Entry *> Result = lookupPath(Path);
+  ErrorOr<RedirectingFileSystem::LookupResult> Result = lookupPath(Path);
   if (!Result) {
-    if (shouldUseExternalFS() &&
-        Result.getError() == llvm::errc::no_such_file_or_directory) {
+    if (shouldFallBackToExternalFS(Result.getError()))
       return ExternalFS->status(Path);
-    }
     return Result.getError();
   }
-  return status(Path, *Result);
+
+  ErrorOr<Status> S = status(Path, *Result);
+  if (!S && shouldFallBackToExternalFS(S.getError(), Result->E))
+    S = ExternalFS->status(Path);
+  return S;
 }
 
 namespace {
@@ -1886,32 +2010,35 @@ RedirectingFileSystem::openFileForRead(const Twine &Path_) {
   if (std::error_code EC = makeCanonical(Path))
     return EC;
 
-  ErrorOr<RedirectingFileSystem::Entry *> E = lookupPath(Path);
-  if (!E) {
-    if (shouldUseExternalFS() &&
-        E.getError() == llvm::errc::no_such_file_or_directory) {
+  ErrorOr<RedirectingFileSystem::LookupResult> Result = lookupPath(Path);
+  if (!Result) {
+    if (shouldFallBackToExternalFS(Result.getError()))
       return ExternalFS->openFileForRead(Path);
-    }
-    return E.getError();
+    return Result.getError();
   }
 
-  auto *F = dyn_cast<RedirectingFileSystem::RedirectingFileEntry>(*E);
-  if (!F) // FIXME: errc::not_a_file?
+  if (!Result->getExternalRedirect()) // FIXME: errc::not_a_file?
     return make_error_code(llvm::errc::invalid_argument);
 
-  auto Result = ExternalFS->openFileForRead(F->getExternalContentsPath());
-  if (!Result)
-    return Result;
+  StringRef ExtRedirect = *Result->getExternalRedirect();
+  auto *RE = cast<RedirectingFileSystem::RemapEntry>(Result->E);
+
+  auto ExternalFile = ExternalFS->openFileForRead(ExtRedirect);
+  if (!ExternalFile) {
+    if (shouldFallBackToExternalFS(ExternalFile.getError(), Result->E))
+      return ExternalFS->openFileForRead(Path);
+    return ExternalFile;
+  }
 
-  auto ExternalStatus = (*Result)->status();
+  auto ExternalStatus = (*ExternalFile)->status();
   if (!ExternalStatus)
     return ExternalStatus.getError();
 
   // FIXME: Update the status with the name and VFSMapped.
-  Status S = getRedirectedFileStatus(Path, F->useExternalName(UseExternalNames),
-                                     *ExternalStatus);
+  Status S = getRedirectedFileStatus(
+      Path, RE->useExternalName(UseExternalNames), *ExternalStatus);
   return std::unique_ptr<File>(
-      std::make_unique<FileWithFixedStatus>(std::move(*Result), S));
+      std::make_unique<FileWithFixedStatus>(std::move(*ExternalFile), S));
 }
 
 std::error_code
@@ -1923,20 +2050,24 @@ RedirectingFileSystem::getRealPath(const Twine &Path_,
   if (std::error_code EC = makeCanonical(Path))
     return EC;
 
-  ErrorOr<RedirectingFileSystem::Entry *> Result = lookupPath(Path);
+  ErrorOr<RedirectingFileSystem::LookupResult> Result = lookupPath(Path);
   if (!Result) {
-    if (shouldUseExternalFS() &&
-        Result.getError() == llvm::errc::no_such_file_or_directory) {
+    if (shouldFallBackToExternalFS(Result.getError()))
       return ExternalFS->getRealPath(Path, Output);
-    }
     return Result.getError();
   }
 
-  if (auto *F =
-          dyn_cast<RedirectingFileSystem::RedirectingFileEntry>(*Result)) {
-    return ExternalFS->getRealPath(F->getExternalContentsPath(), Output);
+  // 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);
+    }
+    return P;
   }
-  // Even if there is a directory entry, fall back to ExternalFS if allowed,
+
+  // 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;
@@ -1957,7 +2088,7 @@ static void getVFSEntries(RedirectingFileSystem::Entry *SrcE,
                           SmallVectorImpl<YAMLVFSEntry> &Entries) {
   auto Kind = SrcE->getKind();
   if (Kind == RedirectingFileSystem::EK_Directory) {
-    auto *DE = dyn_cast<RedirectingFileSystem::RedirectingDirectoryEntry>(SrcE);
+    auto *DE = dyn_cast<RedirectingFileSystem::DirectoryEntry>(SrcE);
     assert(DE && "Must be a directory");
     for (std::unique_ptr<RedirectingFileSystem::Entry> &SubEntry :
          llvm::make_range(DE->contents_begin(), DE->contents_end())) {
@@ -1968,8 +2099,19 @@ static void getVFSEntries(RedirectingFileSystem::Entry *SrcE,
     return;
   }
 
+  if (Kind == RedirectingFileSystem::EK_DirectoryRemap) {
+    auto *DR = dyn_cast<RedirectingFileSystem::DirectoryRemapEntry>(SrcE);
+    assert(DR && "Must be a directory remap");
+    SmallString<128> VPath;
+    for (auto &Comp : Path)
+      llvm::sys::path::append(VPath, Comp);
+    Entries.push_back(
+        YAMLVFSEntry(VPath.c_str(), DR->getExternalContentsPath()));
+    return;
+  }
+
   assert(Kind == RedirectingFileSystem::EK_File && "Must be a EK_File");
-  auto *FE = dyn_cast<RedirectingFileSystem::RedirectingFileEntry>(SrcE);
+  auto *FE = dyn_cast<RedirectingFileSystem::FileEntry>(SrcE);
   assert(FE && "Must be a file");
   SmallString<128> VPath;
   for (auto &Comp : Path)
@@ -1986,12 +2128,15 @@ void vfs::collectVFSFromYAML(std::unique_ptr<MemoryBuffer> Buffer,
   std::unique_ptr<RedirectingFileSystem> VFS = RedirectingFileSystem::create(
       std::move(Buffer), DiagHandler, YAMLFilePath, DiagContext,
       std::move(ExternalFS));
-  ErrorOr<RedirectingFileSystem::Entry *> RootE = VFS->lookupPath("/");
-  if (!RootE)
+  if (!VFS)
+    return;
+  ErrorOr<RedirectingFileSystem::LookupResult> RootResult =
+      VFS->lookupPath("/");
+  if (!RootResult)
     return;
   SmallVector<StringRef, 8> Components;
   Components.push_back("/");
-  getVFSEntries(*RootE, Components, CollectedEntries);
+  getVFSEntries(RootResult->E, Components, CollectedEntries);
 }
 
 UniqueID vfs::getNextVirtualUniqueID() {
@@ -2189,76 +2334,6 @@ void YAMLVFSWriter::write(llvm::raw_ostream &OS) {
                        IsOverlayRelative, OverlayDir);
 }
 
-VFSFromYamlDirIterImpl::VFSFromYamlDirIterImpl(
-    const Twine &_Path,
-    RedirectingFileSystem::RedirectingDirectoryEntry::iterator Begin,
-    RedirectingFileSystem::RedirectingDirectoryEntry::iterator End,
-    bool IterateExternalFS, FileSystem &ExternalFS, std::error_code &EC)
-    : Dir(_Path.str()), Current(Begin), End(End),
-      IterateExternalFS(IterateExternalFS), ExternalFS(ExternalFS) {
-  EC = incrementImpl(/*IsFirstTime=*/true);
-}
-
-std::error_code VFSFromYamlDirIterImpl::increment() {
-  return incrementImpl(/*IsFirstTime=*/false);
-}
-
-std::error_code VFSFromYamlDirIterImpl::incrementExternal() {
-  assert(!(IsExternalFSCurrent && ExternalDirIter == directory_iterator()) &&
-         "incrementing past end");
-  std::error_code EC;
-  if (IsExternalFSCurrent) {
-    ExternalDirIter.increment(EC);
-  } else if (IterateExternalFS) {
-    ExternalDirIter = ExternalFS.dir_begin(Dir, EC);
-    IsExternalFSCurrent = true;
-    if (EC && EC != errc::no_such_file_or_directory)
-      return EC;
-    EC = {};
-  }
-  if (EC || ExternalDirIter == directory_iterator()) {
-    CurrentEntry = directory_entry();
-  } else {
-    CurrentEntry = *ExternalDirIter;
-  }
-  return EC;
-}
-
-std::error_code VFSFromYamlDirIterImpl::incrementContent(bool IsFirstTime) {
-  assert((IsFirstTime || Current != End) && "cannot iterate past end");
-  if (!IsFirstTime)
-    ++Current;
-  while (Current != End) {
-    SmallString<128> PathStr(Dir);
-    llvm::sys::path::append(PathStr, (*Current)->getName());
-    sys::fs::file_type Type = sys::fs::file_type::type_unknown;
-    switch ((*Current)->getKind()) {
-    case RedirectingFileSystem::EK_Directory:
-      Type = sys::fs::file_type::directory_file;
-      break;
-    case RedirectingFileSystem::EK_File:
-      Type = sys::fs::file_type::regular_file;
-      break;
-    }
-    CurrentEntry = directory_entry(std::string(PathStr.str()), Type);
-    return {};
-  }
-  return incrementExternal();
-}
-
-std::error_code VFSFromYamlDirIterImpl::incrementImpl(bool IsFirstTime) {
-  while (true) {
-    std::error_code EC = IsExternalFSCurrent ? incrementExternal()
-                                             : incrementContent(IsFirstTime);
-    if (EC || CurrentEntry.path().empty())
-      return EC;
-    StringRef Name = llvm::sys::path::filename(CurrentEntry.path());
-    if (SeenNames.insert(Name).second)
-      return EC; // name not seen before
-  }
-  llvm_unreachable("returned above");
-}
-
 vfs::recursive_directory_iterator::recursive_directory_iterator(
     FileSystem &FS_, const Twine &Path, std::error_code &EC)
     : FS(&FS_) {