lib/Support/VirtualFileSystem.cpp

   1 //===- VirtualFileSystem.cpp - Virtual File System Layer ------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the VirtualFileSystem interface.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Support/VirtualFileSystem.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/IntrusiveRefCntPtr.h"
  18 #include "llvm/ADT/None.h"
  19 #include "llvm/ADT/Optional.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/ADT/SmallString.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/ADT/StringRef.h"
  24 #include "llvm/ADT/StringSet.h"
  25 #include "llvm/ADT/Twine.h"
  26 #include "llvm/ADT/iterator_range.h"
  27 #include "llvm/Config/llvm-config.h"
  28 #include "llvm/Support/Casting.h"
  29 #include "llvm/Support/Chrono.h"
  30 #include "llvm/Support/Compiler.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/Errc.h"
  33 #include "llvm/Support/ErrorHandling.h"
  34 #include "llvm/Support/ErrorOr.h"
  35 #include "llvm/Support/FileSystem.h"
  36 #include "llvm/Support/MemoryBuffer.h"
  37 #include "llvm/Support/Path.h"
  38 #include "llvm/Support/Process.h"
  39 #include "llvm/Support/SMLoc.h"
  40 #include "llvm/Support/SourceMgr.h"
  41 #include "llvm/Support/YAMLParser.h"
  42 #include "llvm/Support/raw_ostream.h"
  43 #include <algorithm>
  44 #include <atomic>
  45 #include <cassert>
  46 #include <cstdint>
  47 #include <iterator>
  48 #include <limits>
  49 #include <map>
  50 #include <memory>
  51 #include <mutex>
  52 #include <string>
  53 #include <system_error>
  54 #include <utility>
  55 #include <vector>
  56
  57 using namespace llvm;
  58 using namespace llvm::vfs;
  59
  60 using llvm::sys::fs::file_status;
  61 using llvm::sys::fs::file_type;
  62 using llvm::sys::fs::perms;
  63 using llvm::sys::fs::UniqueID;
  64
  65 Status::Status(const file_status &Status)
  66     : UID(Status.getUniqueID()), MTime(Status.getLastModificationTime()),
  67       User(Status.getUser()), Group(Status.getGroup()), Size(Status.getSize()),
  68       Type(Status.type()), Perms(Status.permissions()) {}
  69
  70 Status::Status(StringRef Name, UniqueID UID, sys::TimePoint<> MTime,
  71                uint32_t User, uint32_t Group, uint64_t Size, file_type Type,
  72                perms Perms)
  73     : Name(Name), UID(UID), MTime(MTime), User(User), Group(Group), Size(Size),
  74       Type(Type), Perms(Perms) {}
  75
  76 Status Status::copyWithNewName(const Status &In, StringRef NewName) {
  77   return Status(NewName, In.getUniqueID(), In.getLastModificationTime(),
  78                 In.getUser(), In.getGroup(), In.getSize(), In.getType(),
  79                 In.getPermissions());
  80 }
  81
  82 Status Status::copyWithNewName(const file_status &In, StringRef NewName) {
  83   return Status(NewName, In.getUniqueID(), In.getLastModificationTime(),
  84                 In.getUser(), In.getGroup(), In.getSize(), In.type(),
  85                 In.permissions());
  86 }
  87
  88 bool Status::equivalent(const Status &Other) const {
  89   assert(isStatusKnown() && Other.isStatusKnown());
  90   return getUniqueID() == Other.getUniqueID();
  91 }
  92
  93 bool Status::isDirectory() const { return Type == file_type::directory_file; }
  94
  95 bool Status::isRegularFile() const { return Type == file_type::regular_file; }
  96
  97 bool Status::isOther() const {
  98   return exists() && !isRegularFile() && !isDirectory() && !isSymlink();
  99 }
 100
 101 bool Status::isSymlink() const { return Type == file_type::symlink_file; }
 102
 103 bool Status::isStatusKnown() const { return Type != file_type::status_error; }
 104
 105 bool Status::exists() const {
 106   return isStatusKnown() && Type != file_type::file_not_found;
 107 }
 108
 109 File::~File() = default;
 110
 111 FileSystem::~FileSystem() = default;
 112
 113 ErrorOr<std::unique_ptr<MemoryBuffer>>
 114 FileSystem::getBufferForFile(const llvm::Twine &Name, int64_t FileSize,
 115                              bool RequiresNullTerminator, bool IsVolatile) {
 116   auto F = openFileForRead(Name);
 117   if (!F)
 118     return F.getError();
 119
 120   return (*F)->getBuffer(Name, FileSize, RequiresNullTerminator, IsVolatile);
 121 }
 122
 123 std::error_code FileSystem::makeAbsolute(SmallVectorImpl<char> &Path) const {
 124   if (llvm::sys::path::is_absolute(Path))
 125     return {};
 126
 127   auto WorkingDir = getCurrentWorkingDirectory();
 128   if (!WorkingDir)
 129     return WorkingDir.getError();
 130
 131   return llvm::sys::fs::make_absolute(WorkingDir.get(), Path);
 132 }
 133
 134 std::error_code FileSystem::getRealPath(const Twine &Path,
 135                                         SmallVectorImpl<char> &Output) const {
 136   return errc::operation_not_permitted;
 137 }
 138
 139 std::error_code FileSystem::isLocal(const Twine &Path, bool &Result) {
 140   return errc::operation_not_permitted;
 141 }
 142
 143 bool FileSystem::exists(const Twine &Path) {
 144   auto Status = status(Path);
 145   return Status && Status->exists();
 146 }
 147
 148 #ifndef NDEBUG
 149 static bool isTraversalComponent(StringRef Component) {
 150   return Component.equals("..") || Component.equals(".");
 151 }
 152
 153 static bool pathHasTraversal(StringRef Path) {
 154   using namespace llvm::sys;
 155
 156   for (StringRef Comp : llvm::make_range(path::begin(Path), path::end(Path)))
 157     if (isTraversalComponent(Comp))
 158       return true;
 159   return false;
 160 }
 161 #endif
 162
 163 //===-----------------------------------------------------------------------===/
 164 // RealFileSystem implementation
 165 //===-----------------------------------------------------------------------===/
 166
 167 namespace {
 168
 169 /// Wrapper around a raw file descriptor.
 170 class RealFile : public File {
 171   friend class RealFileSystem;
 172
 173   int FD;
 174   Status S;
 175   std::string RealName;
 176
 177   RealFile(int FD, StringRef NewName, StringRef NewRealPathName)
 178       : FD(FD), S(NewName, {}, {}, {}, {}, {},
 179                   llvm::sys::fs::file_type::status_error, {}),
 180         RealName(NewRealPathName.str()) {
 181     assert(FD >= 0 && "Invalid or inactive file descriptor");
 182   }
 183
 184 public:
 185   ~RealFile() override;
 186
 187   ErrorOr<Status> status() override;
 188   ErrorOr<std::string> getName() override;
 189   ErrorOr<std::unique_ptr<MemoryBuffer>> getBuffer(const Twine &Name,
 190                                                    int64_t FileSize,
 191                                                    bool RequiresNullTerminator,
 192                                                    bool IsVolatile) override;
 193   std::error_code close() override;
 194 };
 195
 196 } // namespace
 197
 198 RealFile::~RealFile() { close(); }
 199
 200 ErrorOr<Status> RealFile::status() {
 201   assert(FD != -1 && "cannot stat closed file");
 202   if (!S.isStatusKnown()) {
 203     file_status RealStatus;
 204     if (std::error_code EC = sys::fs::status(FD, RealStatus))
 205       return EC;
 206     S = Status::copyWithNewName(RealStatus, S.getName());
 207   }
 208   return S;
 209 }
 210
 211 ErrorOr<std::string> RealFile::getName() {
 212   return RealName.empty() ? S.getName().str() : RealName;
 213 }
 214
 215 ErrorOr<std::unique_ptr<MemoryBuffer>>
 216 RealFile::getBuffer(const Twine &Name, int64_t FileSize,
 217                     bool RequiresNullTerminator, bool IsVolatile) {
 218   assert(FD != -1 && "cannot get buffer for closed file");
 219   return MemoryBuffer::getOpenFile(FD, Name, FileSize, RequiresNullTerminator,
 220                                    IsVolatile);
 221 }
 222
 223 std::error_code RealFile::close() {
 224   std::error_code EC = sys::Process::SafelyCloseFileDescriptor(FD);
 225   FD = -1;
 226   return EC;
 227 }
 228
 229 namespace {
 230
 231 /// The file system according to your operating system.
 232 class RealFileSystem : public FileSystem {
 233 public:
 234   ErrorOr<Status> status(const Twine &Path) override;
 235   ErrorOr<std::unique_ptr<File>> openFileForRead(const Twine &Path) override;
 236   directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override;
 237
 238   llvm::ErrorOr<std::string> getCurrentWorkingDirectory() const override;
 239   std::error_code setCurrentWorkingDirectory(const Twine &Path) override;
 240   std::error_code isLocal(const Twine &Path, bool &Result) override;
 241   std::error_code getRealPath(const Twine &Path,
 242                               SmallVectorImpl<char> &Output) const override;
 243
 244 private:
 245   mutable std::mutex CWDMutex;
 246   mutable std::string CWDCache;
 247 };
 248
 249 } // namespace
 250
 251 ErrorOr<Status> RealFileSystem::status(const Twine &Path) {
 252   sys::fs::file_status RealStatus;
 253   if (std::error_code EC = sys::fs::status(Path, RealStatus))
 254     return EC;
 255   return Status::copyWithNewName(RealStatus, Path.str());
 256 }
 257
 258 ErrorOr<std::unique_ptr<File>>
 259 RealFileSystem::openFileForRead(const Twine &Name) {
 260   int FD;
 261   SmallString<256> RealName;
 262   if (std::error_code EC =
 263           sys::fs::openFileForRead(Name, FD, sys::fs::OF_None, &RealName))
 264     return EC;
 265   return std::unique_ptr<File>(new RealFile(FD, Name.str(), RealName.str()));
 266 }
 267
 268 llvm::ErrorOr<std::string> RealFileSystem::getCurrentWorkingDirectory() const {
 269   std::lock_guard<std::mutex> Lock(CWDMutex);
 270   if (!CWDCache.empty())
 271     return CWDCache;
 272   SmallString<256> Dir;
 273   if (std::error_code EC = llvm::sys::fs::current_path(Dir))
 274     return EC;
 275   CWDCache = Dir.str();
 276   return CWDCache;
 277 }
 278
 279 std::error_code RealFileSystem::setCurrentWorkingDirectory(const Twine &Path) {
 280   // FIXME: chdir is thread hostile; on the other hand, creating the same
 281   // behavior as chdir is complex: chdir resolves the path once, thus
 282   // guaranteeing that all subsequent relative path operations work
 283   // on the same path the original chdir resulted in. This makes a
 284   // difference for example on network filesystems, where symlinks might be
 285   // switched during runtime of the tool. Fixing this depends on having a
 286   // file system abstraction that allows openat() style interactions.
 287   if (auto EC = llvm::sys::fs::set_current_path(Path))
 288     return EC;
 289
 290   // Invalidate cache.
 291   std::lock_guard<std::mutex> Lock(CWDMutex);
 292   CWDCache.clear();
 293   return std::error_code();
 294 }
 295
 296 std::error_code RealFileSystem::isLocal(const Twine &Path, bool &Result) {
 297   return llvm::sys::fs::is_local(Path, Result);
 298 }
 299
 300 std::error_code
 301 RealFileSystem::getRealPath(const Twine &Path,
 302                             SmallVectorImpl<char> &Output) const {
 303   return llvm::sys::fs::real_path(Path, Output);
 304 }
 305
 306 IntrusiveRefCntPtr<FileSystem> vfs::getRealFileSystem() {
 307   static IntrusiveRefCntPtr<FileSystem> FS = new RealFileSystem();
 308   return FS;
 309 }
 310
 311 namespace {
 312
 313 class RealFSDirIter : public llvm::vfs::detail::DirIterImpl {
 314   llvm::sys::fs::directory_iterator Iter;
 315
 316 public:
 317   RealFSDirIter(const Twine &Path, std::error_code &EC) : Iter(Path, EC) {
 318     if (Iter != llvm::sys::fs::directory_iterator())
 319       CurrentEntry = directory_entry(Iter->path(), Iter->type());
 320   }
 321
 322   std::error_code increment() override {
 323     std::error_code EC;
 324     Iter.increment(EC);
 325     CurrentEntry = (Iter == llvm::sys::fs::directory_iterator())
 326                        ? directory_entry()
 327                        : directory_entry(Iter->path(), Iter->type());
 328     return EC;
 329   }
 330 };
 331
 332 } // namespace
 333
 334 directory_iterator RealFileSystem::dir_begin(const Twine &Dir,
 335                                              std::error_code &EC) {
 336   return directory_iterator(std::make_shared<RealFSDirIter>(Dir, EC));
 337 }
 338
 339 //===-----------------------------------------------------------------------===/
 340 // OverlayFileSystem implementation
 341 //===-----------------------------------------------------------------------===/
 342
 343 OverlayFileSystem::OverlayFileSystem(IntrusiveRefCntPtr<FileSystem> BaseFS) {
 344   FSList.push_back(std::move(BaseFS));
 345 }
 346
 347 void OverlayFileSystem::pushOverlay(IntrusiveRefCntPtr<FileSystem> FS) {
 348   FSList.push_back(FS);
 349   // Synchronize added file systems by duplicating the working directory from
 350   // the first one in the list.
 351   FS->setCurrentWorkingDirectory(getCurrentWorkingDirectory().get());
 352 }
 353
 354 ErrorOr<Status> OverlayFileSystem::status(const Twine &Path) {
 355   // FIXME: handle symlinks that cross file systems
 356   for (iterator I = overlays_begin(), E = overlays_end(); I != E; ++I) {
 357     ErrorOr<Status> Status = (*I)->status(Path);
 358     if (Status || Status.getError() != llvm::errc::no_such_file_or_directory)
 359       return Status;
 360   }
 361   return make_error_code(llvm::errc::no_such_file_or_directory);
 362 }
 363
 364 ErrorOr<std::unique_ptr<File>>
 365 OverlayFileSystem::openFileForRead(const llvm::Twine &Path) {
 366   // FIXME: handle symlinks that cross file systems
 367   for (iterator I = overlays_begin(), E = overlays_end(); I != E; ++I) {
 368     auto Result = (*I)->openFileForRead(Path);
 369     if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
 370       return Result;
 371   }
 372   return make_error_code(llvm::errc::no_such_file_or_directory);
 373 }
 374
 375 llvm::ErrorOr<std::string>
 376 OverlayFileSystem::getCurrentWorkingDirectory() const {
 377   // All file systems are synchronized, just take the first working directory.
 378   return FSList.front()->getCurrentWorkingDirectory();
 379 }
 380
 381 std::error_code
 382 OverlayFileSystem::setCurrentWorkingDirectory(const Twine &Path) {
 383   for (auto &FS : FSList)
 384     if (std::error_code EC = FS->setCurrentWorkingDirectory(Path))
 385       return EC;
 386   return {};
 387 }
 388
 389 std::error_code OverlayFileSystem::isLocal(const Twine &Path, bool &Result) {
 390   for (auto &FS : FSList)
 391     if (FS->exists(Path))
 392       return FS->isLocal(Path, Result);
 393   return errc::no_such_file_or_directory;
 394 }
 395
 396 std::error_code
 397 OverlayFileSystem::getRealPath(const Twine &Path,
 398                                SmallVectorImpl<char> &Output) const {
 399   for (auto &FS : FSList)
 400     if (FS->exists(Path))
 401       return FS->getRealPath(Path, Output);
 402   return errc::no_such_file_or_directory;
 403 }
 404
 405 llvm::vfs::detail::DirIterImpl::~DirIterImpl() = default;
 406
 407 namespace {
 408
 409 class OverlayFSDirIterImpl : public llvm::vfs::detail::DirIterImpl {
 410   OverlayFileSystem &Overlays;
 411   std::string Path;
 412   OverlayFileSystem::iterator CurrentFS;
 413   directory_iterator CurrentDirIter;
 414   llvm::StringSet<> SeenNames;
 415
 416   std::error_code incrementFS() {
 417     assert(CurrentFS != Overlays.overlays_end() && "incrementing past end");
 418     ++CurrentFS;
 419     for (auto E = Overlays.overlays_end(); CurrentFS != E; ++CurrentFS) {
 420       std::error_code EC;
 421       CurrentDirIter = (*CurrentFS)->dir_begin(Path, EC);
 422       if (EC && EC != errc::no_such_file_or_directory)
 423         return EC;
 424       if (CurrentDirIter != directory_iterator())
 425         break; // found
 426     }
 427     return {};
 428   }
 429
 430   std::error_code incrementDirIter(bool IsFirstTime) {
 431     assert((IsFirstTime || CurrentDirIter != directory_iterator()) &&
 432            "incrementing past end");
 433     std::error_code EC;
 434     if (!IsFirstTime)
 435       CurrentDirIter.increment(EC);
 436     if (!EC && CurrentDirIter == directory_iterator())
 437       EC = incrementFS();
 438     return EC;
 439   }
 440
 441   std::error_code incrementImpl(bool IsFirstTime) {
 442     while (true) {
 443       std::error_code EC = incrementDirIter(IsFirstTime);
 444       if (EC || CurrentDirIter == directory_iterator()) {
 445         CurrentEntry = directory_entry();
 446         return EC;
 447       }
 448       CurrentEntry = *CurrentDirIter;
 449       StringRef Name = llvm::sys::path::filename(CurrentEntry.path());
 450       if (SeenNames.insert(Name).second)
 451         return EC; // name not seen before
 452     }
 453     llvm_unreachable("returned above");
 454   }
 455
 456 public:
 457   OverlayFSDirIterImpl(const Twine &Path, OverlayFileSystem &FS,
 458                        std::error_code &EC)
 459       : Overlays(FS), Path(Path.str()), CurrentFS(Overlays.overlays_begin()) {
 460     CurrentDirIter = (*CurrentFS)->dir_begin(Path, EC);
 461     EC = incrementImpl(true);
 462   }
 463
 464   std::error_code increment() override { return incrementImpl(false); }
 465 };
 466
 467 } // namespace
 468
 469 directory_iterator OverlayFileSystem::dir_begin(const Twine &Dir,
 470                                                 std::error_code &EC) {
 471   return directory_iterator(
 472       std::make_shared<OverlayFSDirIterImpl>(Dir, *this, EC));
 473 }
 474
 475 void ProxyFileSystem::anchor() {}
 476
 477 namespace llvm {
 478 namespace vfs {
 479
 480 namespace detail {
 481
 482 enum InMemoryNodeKind { IME_File, IME_Directory, IME_HardLink };
 483
 484 /// The in memory file system is a tree of Nodes. Every node can either be a
 485 /// file , hardlink or a directory.
 486 class InMemoryNode {
 487   InMemoryNodeKind Kind;
 488   std::string FileName;
 489
 490 public:
 491   InMemoryNode(llvm::StringRef FileName, InMemoryNodeKind Kind)
 492       : Kind(Kind), FileName(llvm::sys::path::filename(FileName)) {}
 493   virtual ~InMemoryNode() = default;
 494
 495   /// Get the filename of this node (the name without the directory part).
 496   StringRef getFileName() const { return FileName; }
 497   InMemoryNodeKind getKind() const { return Kind; }
 498   virtual std::string toString(unsigned Indent) const = 0;
 499 };
 500
 501 class InMemoryFile : public InMemoryNode {
 502   Status Stat;
 503   std::unique_ptr<llvm::MemoryBuffer> Buffer;
 504
 505 public:
 506   InMemoryFile(Status Stat, std::unique_ptr<llvm::MemoryBuffer> Buffer)
 507       : InMemoryNode(Stat.getName(), IME_File), Stat(std::move(Stat)),
 508         Buffer(std::move(Buffer)) {}
 509
 510   /// Return the \p Status for this node. \p RequestedName should be the name
 511   /// through which the caller referred to this node. It will override
 512   /// \p Status::Name in the return value, to mimic the behavior of \p RealFile.
 513   Status getStatus(StringRef RequestedName) const {
 514     return Status::copyWithNewName(Stat, RequestedName);
 515   }
 516   llvm::MemoryBuffer *getBuffer() const { return Buffer.get(); }
 517
 518   std::string toString(unsigned Indent) const override {
 519     return (std::string(Indent, ' ') + Stat.getName() + "\n").str();
 520   }
 521
 522   static bool classof(const InMemoryNode *N) {
 523     return N->getKind() == IME_File;
 524   }
 525 };
 526
 527 namespace {
 528
 529 class InMemoryHardLink : public InMemoryNode {
 530   const InMemoryFile &ResolvedFile;
 531
 532 public:
 533   InMemoryHardLink(StringRef Path, const InMemoryFile &ResolvedFile)
 534       : InMemoryNode(Path, IME_HardLink), ResolvedFile(ResolvedFile) {}
 535   const InMemoryFile &getResolvedFile() const { return ResolvedFile; }
 536
 537   std::string toString(unsigned Indent) const override {
 538     return std::string(Indent, ' ') + "HardLink to -> " +
 539            ResolvedFile.toString(0);
 540   }
 541
 542   static bool classof(const InMemoryNode *N) {
 543     return N->getKind() == IME_HardLink;
 544   }
 545 };
 546
 547 /// Adapt a InMemoryFile for VFS' File interface.  The goal is to make
 548 /// \p InMemoryFileAdaptor mimic as much as possible the behavior of
 549 /// \p RealFile.
 550 class InMemoryFileAdaptor : public File {
 551   const InMemoryFile &Node;
 552   /// The name to use when returning a Status for this file.
 553   std::string RequestedName;
 554
 555 public:
 556   explicit InMemoryFileAdaptor(const InMemoryFile &Node,
 557                                std::string RequestedName)
 558       : Node(Node), RequestedName(std::move(RequestedName)) {}
 559
 560   llvm::ErrorOr<Status> status() override {
 561     return Node.getStatus(RequestedName);
 562   }
 563
 564   llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
 565   getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,
 566             bool IsVolatile) override {
 567     llvm::MemoryBuffer *Buf = Node.getBuffer();
 568     return llvm::MemoryBuffer::getMemBuffer(
 569         Buf->getBuffer(), Buf->getBufferIdentifier(), RequiresNullTerminator);
 570   }
 571
 572   std::error_code close() override { return {}; }
 573 };
 574 } // namespace
 575
 576 class InMemoryDirectory : public InMemoryNode {
 577   Status Stat;
 578   llvm::StringMap<std::unique_ptr<InMemoryNode>> Entries;
 579
 580 public:
 581   InMemoryDirectory(Status Stat)
 582       : InMemoryNode(Stat.getName(), IME_Directory), Stat(std::move(Stat)) {}
 583
 584   /// Return the \p Status for this node. \p RequestedName should be the name
 585   /// through which the caller referred to this node. It will override
 586   /// \p Status::Name in the return value, to mimic the behavior of \p RealFile.
 587   Status getStatus(StringRef RequestedName) const {
 588     return Status::copyWithNewName(Stat, RequestedName);
 589   }
 590   InMemoryNode *getChild(StringRef Name) {
 591     auto I = Entries.find(Name);
 592     if (I != Entries.end())
 593       return I->second.get();
 594     return nullptr;
 595   }
 596
 597   InMemoryNode *addChild(StringRef Name, std::unique_ptr<InMemoryNode> Child) {
 598     return Entries.insert(make_pair(Name, std::move(Child)))
 599         .first->second.get();
 600   }
 601
 602   using const_iterator = decltype(Entries)::const_iterator;
 603
 604   const_iterator begin() const { return Entries.begin(); }
 605   const_iterator end() const { return Entries.end(); }
 606
 607   std::string toString(unsigned Indent) const override {
 608     std::string Result =
 609         (std::string(Indent, ' ') + Stat.getName() + "\n").str();
 610     for (const auto &Entry : Entries)
 611       Result += Entry.second->toString(Indent + 2);
 612     return Result;
 613   }
 614
 615   static bool classof(const InMemoryNode *N) {
 616     return N->getKind() == IME_Directory;
 617   }
 618 };
 619
 620 namespace {
 621 Status getNodeStatus(const InMemoryNode *Node, StringRef RequestedName) {
 622   if (auto Dir = dyn_cast<detail::InMemoryDirectory>(Node))
 623     return Dir->getStatus(RequestedName);
 624   if (auto File = dyn_cast<detail::InMemoryFile>(Node))
 625     return File->getStatus(RequestedName);
 626   if (auto Link = dyn_cast<detail::InMemoryHardLink>(Node))
 627     return Link->getResolvedFile().getStatus(RequestedName);
 628   llvm_unreachable("Unknown node type");
 629 }
 630 } // namespace
 631 } // namespace detail
 632
 633 InMemoryFileSystem::InMemoryFileSystem(bool UseNormalizedPaths)
 634     : Root(new detail::InMemoryDirectory(
 635           Status("", getNextVirtualUniqueID(), llvm::sys::TimePoint<>(), 0, 0,
 636                  0, llvm::sys::fs::file_type::directory_file,
 637                  llvm::sys::fs::perms::all_all))),
 638       UseNormalizedPaths(UseNormalizedPaths) {}
 639
 640 InMemoryFileSystem::~InMemoryFileSystem() = default;
 641
 642 std::string InMemoryFileSystem::toString() const {
 643   return Root->toString(/*Indent=*/0);
 644 }
 645
 646 bool InMemoryFileSystem::addFile(const Twine &P, time_t ModificationTime,
 647                                  std::unique_ptr<llvm::MemoryBuffer> Buffer,
 648                                  Optional<uint32_t> User,
 649                                  Optional<uint32_t> Group,
 650                                  Optional<llvm::sys::fs::file_type> Type,
 651                                  Optional<llvm::sys::fs::perms> Perms,
 652                                  const detail::InMemoryFile *HardLinkTarget) {
 653   SmallString<128> Path;
 654   P.toVector(Path);
 655
 656   // Fix up relative paths. This just prepends the current working directory.
 657   std::error_code EC = makeAbsolute(Path);
 658   assert(!EC);
 659   (void)EC;
 660
 661   if (useNormalizedPaths())
 662     llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
 663
 664   if (Path.empty())
 665     return false;
 666
 667   detail::InMemoryDirectory *Dir = Root.get();
 668   auto I = llvm::sys::path::begin(Path), E = sys::path::end(Path);
 669   const auto ResolvedUser = User.getValueOr(0);
 670   const auto ResolvedGroup = Group.getValueOr(0);
 671   const auto ResolvedType = Type.getValueOr(sys::fs::file_type::regular_file);
 672   const auto ResolvedPerms = Perms.getValueOr(sys::fs::all_all);
 673   assert(!(HardLinkTarget && Buffer) && "HardLink cannot have a buffer");
 674   // Any intermediate directories we create should be accessible by
 675   // the owner, even if Perms says otherwise for the final path.
 676   const auto NewDirectoryPerms = ResolvedPerms | sys::fs::owner_all;
 677   while (true) {
 678     StringRef Name = *I;
 679     detail::InMemoryNode *Node = Dir->getChild(Name);
 680     ++I;
 681     if (!Node) {
 682       if (I == E) {
 683         // End of the path.
 684         std::unique_ptr<detail::InMemoryNode> Child;
 685         if (HardLinkTarget)
 686           Child.reset(new detail::InMemoryHardLink(P.str(), *HardLinkTarget));
 687         else {
 688           // Create a new file or directory.
 689           Status Stat(P.str(), getNextVirtualUniqueID(),
 690                       llvm::sys::toTimePoint(ModificationTime), ResolvedUser,
 691                       ResolvedGroup, Buffer->getBufferSize(), ResolvedType,
 692                       ResolvedPerms);
 693           if (ResolvedType == sys::fs::file_type::directory_file) {
 694             Child.reset(new detail::InMemoryDirectory(std::move(Stat)));
 695           } else {
 696             Child.reset(
 697                 new detail::InMemoryFile(std::move(Stat), std::move(Buffer)));
 698           }
 699         }
 700         Dir->addChild(Name, std::move(Child));
 701         return true;
 702       }
 703
 704       // Create a new directory. Use the path up to here.
 705       Status Stat(
 706           StringRef(Path.str().begin(), Name.end() - Path.str().begin()),
 707           getNextVirtualUniqueID(), llvm::sys::toTimePoint(ModificationTime),
 708           ResolvedUser, ResolvedGroup, 0, sys::fs::file_type::directory_file,
 709           NewDirectoryPerms);
 710       Dir = cast<detail::InMemoryDirectory>(Dir->addChild(
 711           Name, llvm::make_unique<detail::InMemoryDirectory>(std::move(Stat))));
 712       continue;
 713     }
 714
 715     if (auto *NewDir = dyn_cast<detail::InMemoryDirectory>(Node)) {
 716       Dir = NewDir;
 717     } else {
 718       assert((isa<detail::InMemoryFile>(Node) ||
 719               isa<detail::InMemoryHardLink>(Node)) &&
 720              "Must be either file, hardlink or directory!");
 721
 722       // Trying to insert a directory in place of a file.
 723       if (I != E)
 724         return false;
 725
 726       // Return false only if the new file is different from the existing one.
 727       if (auto Link = dyn_cast<detail::InMemoryHardLink>(Node)) {
 728         return Link->getResolvedFile().getBuffer()->getBuffer() ==
 729                Buffer->getBuffer();
 730       }
 731       return cast<detail::InMemoryFile>(Node)->getBuffer()->getBuffer() ==
 732              Buffer->getBuffer();
 733     }
 734   }
 735 }
 736
 737 bool InMemoryFileSystem::addFile(const Twine &P, time_t ModificationTime,
 738                                  std::unique_ptr<llvm::MemoryBuffer> Buffer,
 739                                  Optional<uint32_t> User,
 740                                  Optional<uint32_t> Group,
 741                                  Optional<llvm::sys::fs::file_type> Type,
 742                                  Optional<llvm::sys::fs::perms> Perms) {
 743   return addFile(P, ModificationTime, std::move(Buffer), User, Group, Type,
 744                  Perms, /*HardLinkTarget=*/nullptr);
 745 }
 746
 747 bool InMemoryFileSystem::addFileNoOwn(const Twine &P, time_t ModificationTime,
 748                                       llvm::MemoryBuffer *Buffer,
 749                                       Optional<uint32_t> User,
 750                                       Optional<uint32_t> Group,
 751                                       Optional<llvm::sys::fs::file_type> Type,
 752                                       Optional<llvm::sys::fs::perms> Perms) {
 753   return addFile(P, ModificationTime,
 754                  llvm::MemoryBuffer::getMemBuffer(
 755                      Buffer->getBuffer(), Buffer->getBufferIdentifier()),
 756                  std::move(User), std::move(Group), std::move(Type),
 757                  std::move(Perms));
 758 }
 759
 760 static ErrorOr<const detail::InMemoryNode *>
 761 lookupInMemoryNode(const InMemoryFileSystem &FS, detail::InMemoryDirectory *Dir,
 762                    const Twine &P) {
 763   SmallString<128> Path;
 764   P.toVector(Path);
 765
 766   // Fix up relative paths. This just prepends the current working directory.
 767   std::error_code EC = FS.makeAbsolute(Path);
 768   assert(!EC);
 769   (void)EC;
 770
 771   if (FS.useNormalizedPaths())
 772     llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
 773
 774   if (Path.empty())
 775     return Dir;
 776
 777   auto I = llvm::sys::path::begin(Path), E = llvm::sys::path::end(Path);
 778   while (true) {
 779     detail::InMemoryNode *Node = Dir->getChild(*I);
 780     ++I;
 781     if (!Node)
 782       return errc::no_such_file_or_directory;
 783
 784     // Return the file if it's at the end of the path.
 785     if (auto File = dyn_cast<detail::InMemoryFile>(Node)) {
 786       if (I == E)
 787         return File;
 788       return errc::no_such_file_or_directory;
 789     }
 790
 791     // If Node is HardLink then return the resolved file.
 792     if (auto File = dyn_cast<detail::InMemoryHardLink>(Node)) {
 793       if (I == E)
 794         return &File->getResolvedFile();
 795       return errc::no_such_file_or_directory;
 796     }
 797     // Traverse directories.
 798     Dir = cast<detail::InMemoryDirectory>(Node);
 799     if (I == E)
 800       return Dir;
 801   }
 802 }
 803
 804 bool InMemoryFileSystem::addHardLink(const Twine &FromPath,
 805                                      const Twine &ToPath) {
 806   auto FromNode = lookupInMemoryNode(*this, Root.get(), FromPath);
 807   auto ToNode = lookupInMemoryNode(*this, Root.get(), ToPath);
 808   // FromPath must not have been added before. ToPath must have been added
 809   // before. Resolved ToPath must be a File.
 810   if (!ToNode || FromNode || !isa<detail::InMemoryFile>(*ToNode))
 811     return false;
 812   return this->addFile(FromPath, 0, nullptr, None, None, None, None,
 813                        cast<detail::InMemoryFile>(*ToNode));
 814 }
 815
 816 llvm::ErrorOr<Status> InMemoryFileSystem::status(const Twine &Path) {
 817   auto Node = lookupInMemoryNode(*this, Root.get(), Path);
 818   if (Node)
 819     return detail::getNodeStatus(*Node, Path.str());
 820   return Node.getError();
 821 }
 822
 823 llvm::ErrorOr<std::unique_ptr<File>>
 824 InMemoryFileSystem::openFileForRead(const Twine &Path) {
 825   auto Node = lookupInMemoryNode(*this, Root.get(), Path);
 826   if (!Node)
 827     return Node.getError();
 828
 829   // When we have a file provide a heap-allocated wrapper for the memory buffer
 830   // to match the ownership semantics for File.
 831   if (auto *F = dyn_cast<detail::InMemoryFile>(*Node))
 832     return std::unique_ptr<File>(
 833         new detail::InMemoryFileAdaptor(*F, Path.str()));
 834
 835   // FIXME: errc::not_a_file?
 836   return make_error_code(llvm::errc::invalid_argument);
 837 }
 838
 839 namespace {
 840
 841 /// Adaptor from InMemoryDir::iterator to directory_iterator.
 842 class InMemoryDirIterator : public llvm::vfs::detail::DirIterImpl {
 843   detail::InMemoryDirectory::const_iterator I;
 844   detail::InMemoryDirectory::const_iterator E;
 845   std::string RequestedDirName;
 846
 847   void setCurrentEntry() {
 848     if (I != E) {
 849       SmallString<256> Path(RequestedDirName);
 850       llvm::sys::path::append(Path, I->second->getFileName());
 851       sys::fs::file_type Type;
 852       switch (I->second->getKind()) {
 853       case detail::IME_File:
 854       case detail::IME_HardLink:
 855         Type = sys::fs::file_type::regular_file;
 856         break;
 857       case detail::IME_Directory:
 858         Type = sys::fs::file_type::directory_file;
 859         break;
 860       }
 861       CurrentEntry = directory_entry(Path.str(), Type);
 862     } else {
 863       // When we're at the end, make CurrentEntry invalid and DirIterImpl will
 864       // do the rest.
 865       CurrentEntry = directory_entry();
 866     }
 867   }
 868
 869 public:
 870   InMemoryDirIterator() = default;
 871
 872   explicit InMemoryDirIterator(const detail::InMemoryDirectory &Dir,
 873                                std::string RequestedDirName)
 874       : I(Dir.begin()), E(Dir.end()),
 875         RequestedDirName(std::move(RequestedDirName)) {
 876     setCurrentEntry();
 877   }
 878
 879   std::error_code increment() override {
 880     ++I;
 881     setCurrentEntry();
 882     return {};
 883   }
 884 };
 885
 886 } // namespace
 887
 888 directory_iterator InMemoryFileSystem::dir_begin(const Twine &Dir,
 889                                                  std::error_code &EC) {
 890   auto Node = lookupInMemoryNode(*this, Root.get(), Dir);
 891   if (!Node) {
 892     EC = Node.getError();
 893     return directory_iterator(std::make_shared<InMemoryDirIterator>());
 894   }
 895
 896   if (auto *DirNode = dyn_cast<detail::InMemoryDirectory>(*Node))
 897     return directory_iterator(
 898         std::make_shared<InMemoryDirIterator>(*DirNode, Dir.str()));
 899
 900   EC = make_error_code(llvm::errc::not_a_directory);
 901   return directory_iterator(std::make_shared<InMemoryDirIterator>());
 902 }
 903
 904 std::error_code InMemoryFileSystem::setCurrentWorkingDirectory(const Twine &P) {
 905   SmallString<128> Path;
 906   P.toVector(Path);
 907
 908   // Fix up relative paths. This just prepends the current working directory.
 909   std::error_code EC = makeAbsolute(Path);
 910   assert(!EC);
 911   (void)EC;
 912
 913   if (useNormalizedPaths())
 914     llvm::sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
 915
 916   if (!Path.empty())
 917     WorkingDirectory = Path.str();
 918   return {};
 919 }
 920
 921 std::error_code
 922 InMemoryFileSystem::getRealPath(const Twine &Path,
 923                                 SmallVectorImpl<char> &Output) const {
 924   auto CWD = getCurrentWorkingDirectory();
 925   if (!CWD || CWD->empty())
 926     return errc::operation_not_permitted;
 927   Path.toVector(Output);
 928   if (auto EC = makeAbsolute(Output))
 929     return EC;
 930   llvm::sys::path::remove_dots(Output, /*remove_dot_dot=*/true);
 931   return {};
 932 }
 933
 934 std::error_code InMemoryFileSystem::isLocal(const Twine &Path, bool &Result) {
 935   Result = false;
 936   return {};
 937 }
 938
 939 } // namespace vfs
 940 } // namespace llvm
 941
 942 //===-----------------------------------------------------------------------===/
 943 // RedirectingFileSystem implementation
 944 //===-----------------------------------------------------------------------===/
 945
 946 namespace {
 947
 948 enum EntryKind { EK_Directory, EK_File };
 949
 950 /// A single file or directory in the VFS.
 951 class Entry {
 952   EntryKind Kind;
 953   std::string Name;
 954
 955 public:
 956   Entry(EntryKind K, StringRef Name) : Kind(K), Name(Name) {}
 957   virtual ~Entry() = default;
 958
 959   StringRef getName() const { return Name; }
 960   EntryKind getKind() const { return Kind; }
 961 };
 962
 963 class RedirectingDirectoryEntry : public Entry {
 964   std::vector<std::unique_ptr<Entry>> Contents;
 965   Status S;
 966
 967 public:
 968   RedirectingDirectoryEntry(StringRef Name,
 969                             std::vector<std::unique_ptr<Entry>> Contents,
 970                             Status S)
 971       : Entry(EK_Directory, Name), Contents(std::move(Contents)),
 972         S(std::move(S)) {}
 973   RedirectingDirectoryEntry(StringRef Name, Status S)
 974       : Entry(EK_Directory, Name), S(std::move(S)) {}
 975
 976   Status getStatus() { return S; }
 977
 978   void addContent(std::unique_ptr<Entry> Content) {
 979     Contents.push_back(std::move(Content));
 980   }
 981
 982   Entry *getLastContent() const { return Contents.back().get(); }
 983
 984   using iterator = decltype(Contents)::iterator;
 985
 986   iterator contents_begin() { return Contents.begin(); }
 987   iterator contents_end() { return Contents.end(); }
 988
 989   static bool classof(const Entry *E) { return E->getKind() == EK_Directory; }
 990 };
 991
 992 class RedirectingFileEntry : public Entry {
 993 public:
 994   enum NameKind { NK_NotSet, NK_External, NK_Virtual };
 995
 996 private:
 997   std::string ExternalContentsPath;
 998   NameKind UseName;
 999
1000 public:
1001   RedirectingFileEntry(StringRef Name, StringRef ExternalContentsPath,
1002                        NameKind UseName)
1003       : Entry(EK_File, Name), ExternalContentsPath(ExternalContentsPath),
1004         UseName(UseName) {}
1005
1006   StringRef getExternalContentsPath() const { return ExternalContentsPath; }
1007
1008   /// whether to use the external path as the name for this file.
1009   bool useExternalName(bool GlobalUseExternalName) const {
1010     return UseName == NK_NotSet ? GlobalUseExternalName
1011                                 : (UseName == NK_External);
1012   }
1013
1014   NameKind getUseName() const { return UseName; }
1015
1016   static bool classof(const Entry *E) { return E->getKind() == EK_File; }
1017 };
1018
1019 // FIXME: reuse implementation common with OverlayFSDirIterImpl as these
1020 // iterators are conceptually similar.
1021 class VFSFromYamlDirIterImpl : public llvm::vfs::detail::DirIterImpl {
1022   std::string Dir;
1023   RedirectingDirectoryEntry::iterator Current, End;
1024
1025   // To handle 'fallthrough' mode we need to iterate at first through
1026   // RedirectingDirectoryEntry and then through ExternalFS. These operations are
1027   // done sequentially, we just need to keep a track of what kind of iteration
1028   // we are currently performing.
1029
1030   /// Flag telling if we should iterate through ExternalFS or stop at the last
1031   /// RedirectingDirectoryEntry::iterator.
1032   bool IterateExternalFS;
1033   /// Flag telling if we have switched to iterating through ExternalFS.
1034   bool IsExternalFSCurrent = false;
1035   FileSystem &ExternalFS;
1036   directory_iterator ExternalDirIter;
1037   llvm::StringSet<> SeenNames;
1038
1039   /// To combine multiple iterations, different methods are responsible for
1040   /// different iteration steps.
1041   /// @{
1042
1043   /// Responsible for dispatching between RedirectingDirectoryEntry iteration
1044   /// and ExternalFS iteration.
1045   std::error_code incrementImpl(bool IsFirstTime);
1046   /// Responsible for RedirectingDirectoryEntry iteration.
1047   std::error_code incrementContent(bool IsFirstTime);
1048   /// Responsible for ExternalFS iteration.
1049   std::error_code incrementExternal();
1050   /// @}
1051
1052 public:
1053   VFSFromYamlDirIterImpl(const Twine &Path,
1054                          RedirectingDirectoryEntry::iterator Begin,
1055                          RedirectingDirectoryEntry::iterator End,
1056                          bool IterateExternalFS, FileSystem &ExternalFS,
1057                          std::error_code &EC);
1058
1059   std::error_code increment() override;
1060 };
1061
1062 /// A virtual file system parsed from a YAML file.
1063 ///
1064 /// Currently, this class allows creating virtual directories and mapping
1065 /// virtual file paths to existing external files, available in \c ExternalFS.
1066 ///
1067 /// The basic structure of the parsed file is:
1068 /// \verbatim
1069 /// {
1070 ///   'version': <version number>,
1071 ///   <optional configuration>
1072 ///   'roots': [
1073 ///              <directory entries>
1074 ///            ]
1075 /// }
1076 /// \endverbatim
1077 ///
1078 /// All configuration options are optional.
1079 ///   'case-sensitive': <boolean, default=true>
1080 ///   'use-external-names': <boolean, default=true>
1081 ///   'overlay-relative': <boolean, default=false>
1082 ///   'fallthrough': <boolean, default=true>
1083 ///
1084 /// Virtual directories are represented as
1085 /// \verbatim
1086 /// {
1087 ///   'type': 'directory',
1088 ///   'name': <string>,
1089 ///   'contents': [ <file or directory entries> ]
1090 /// }
1091 /// \endverbatim
1092 ///
1093 /// The default attributes for virtual directories are:
1094 /// \verbatim
1095 /// MTime = now() when created
1096 /// Perms = 0777
1097 /// User = Group = 0
1098 /// Size = 0
1099 /// UniqueID = unspecified unique value
1100 /// \endverbatim
1101 ///
1102 /// Re-mapped files are represented as
1103 /// \verbatim
1104 /// {
1105 ///   'type': 'file',
1106 ///   'name': <string>,
1107 ///   'use-external-name': <boolean> # Optional
1108 ///   'external-contents': <path to external file>
1109 /// }
1110 /// \endverbatim
1111 ///
1112 /// and inherit their attributes from the external contents.
1113 ///
1114 /// In both cases, the 'name' field may contain multiple path components (e.g.
1115 /// /path/to/file). However, any directory that contains more than one child
1116 /// must be uniquely represented by a directory entry.
1117 class RedirectingFileSystem : public vfs::FileSystem {
1118   friend class RedirectingFileSystemParser;
1119
1120   /// The root(s) of the virtual file system.
1121   std::vector<std::unique_ptr<Entry>> Roots;
1122
1123   /// The file system to use for external references.
1124   IntrusiveRefCntPtr<FileSystem> ExternalFS;
1125
1126   /// If IsRelativeOverlay is set, this represents the directory
1127   /// path that should be prefixed to each 'external-contents' entry
1128   /// when reading from YAML files.
1129   std::string ExternalContentsPrefixDir;
1130
1131   /// @name Configuration
1132   /// @{
1133
1134   /// Whether to perform case-sensitive comparisons.
1135   ///
1136   /// Currently, case-insensitive matching only works correctly with ASCII.
1137   bool CaseSensitive = true;
1138
1139   /// IsRelativeOverlay marks whether a ExternalContentsPrefixDir path must
1140   /// be prefixed in every 'external-contents' when reading from YAML files.
1141   bool IsRelativeOverlay = false;
1142
1143   /// Whether to use to use the value of 'external-contents' for the
1144   /// names of files.  This global value is overridable on a per-file basis.
1145   bool UseExternalNames = true;
1146
1147   /// Whether to attempt a file lookup in external file system after it wasn't
1148   /// found in VFS.
1149   bool IsFallthrough = true;
1150   /// @}
1151
1152   /// Virtual file paths and external files could be canonicalized without "..",
1153   /// "." and "./" in their paths. FIXME: some unittests currently fail on
1154   /// win32 when using remove_dots and remove_leading_dotslash on paths.
1155   bool UseCanonicalizedPaths =
1156 #ifdef _WIN32
1157       false;
1158 #else
1159       true;
1160 #endif
1161
1162 private:
1163   RedirectingFileSystem(IntrusiveRefCntPtr<FileSystem> ExternalFS)
1164       : ExternalFS(std::move(ExternalFS)) {}
1165
1166   /// Looks up the path <tt>[Start, End)</tt> in \p From, possibly
1167   /// recursing into the contents of \p From if it is a directory.
1168   ErrorOr<Entry *> lookupPath(sys::path::const_iterator Start,
1169                               sys::path::const_iterator End, Entry *From) const;
1170
1171   /// Get the status of a given an \c Entry.
1172   ErrorOr<Status> status(const Twine &Path, Entry *E);
1173
1174 public:
1175   /// Looks up \p Path in \c Roots.
1176   ErrorOr<Entry *> lookupPath(const Twine &Path) const;
1177
1178   /// Parses \p Buffer, which is expected to be in YAML format and
1179   /// returns a virtual file system representing its contents.
1180   static RedirectingFileSystem *
1181   create(std::unique_ptr<MemoryBuffer> Buffer,
1182          SourceMgr::DiagHandlerTy DiagHandler, StringRef YAMLFilePath,
1183          void *DiagContext, IntrusiveRefCntPtr<FileSystem> ExternalFS);
1184
1185   ErrorOr<Status> status(const Twine &Path) override;
1186   ErrorOr<std::unique_ptr<File>> openFileForRead(const Twine &Path) override;
1187
1188   std::error_code getRealPath(const Twine &Path,
1189                               SmallVectorImpl<char> &Output) const override;
1190
1191   llvm::ErrorOr<std::string> getCurrentWorkingDirectory() const override {
1192     return ExternalFS->getCurrentWorkingDirectory();
1193   }
1194
1195   std::error_code setCurrentWorkingDirectory(const Twine &Path) override {
1196     return ExternalFS->setCurrentWorkingDirectory(Path);
1197   }
1198
1199   std::error_code isLocal(const Twine &Path, bool &Result) override {
1200     return ExternalFS->isLocal(Path, Result);
1201   }
1202
1203   directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override {
1204     ErrorOr<Entry *> E = lookupPath(Dir);
1205     if (!E) {
1206       EC = E.getError();
1207       if (IsFallthrough && EC == errc::no_such_file_or_directory)
1208         return ExternalFS->dir_begin(Dir, EC);
1209       return {};
1210     }
1211     ErrorOr<Status> S = status(Dir, *E);
1212     if (!S) {
1213       EC = S.getError();
1214       return {};
1215     }
1216     if (!S->isDirectory()) {
1217       EC = std::error_code(static_cast<int>(errc::not_a_directory),
1218                            std::system_category());
1219       return {};
1220     }
1221
1222     auto *D = cast<RedirectingDirectoryEntry>(*E);
1223     return directory_iterator(std::make_shared<VFSFromYamlDirIterImpl>(
1224         Dir, D->contents_begin(), D->contents_end(),
1225         /*IterateExternalFS=*/IsFallthrough, *ExternalFS, EC));
1226   }
1227
1228   void setExternalContentsPrefixDir(StringRef PrefixDir) {
1229     ExternalContentsPrefixDir = PrefixDir.str();
1230   }
1231
1232   StringRef getExternalContentsPrefixDir() const {
1233     return ExternalContentsPrefixDir;
1234   }
1235
1236 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1237   LLVM_DUMP_METHOD void dump() const {
1238     for (const auto &Root : Roots)
1239       dumpEntry(Root.get());
1240   }
1241
1242   LLVM_DUMP_METHOD void dumpEntry(Entry *E, int NumSpaces = 0) const {
1243     StringRef Name = E->getName();
1244     for (int i = 0, e = NumSpaces; i < e; ++i)
1245       dbgs() << " ";
1246     dbgs() << "'" << Name.str().c_str() << "'"
1247            << "\n";
1248
1249     if (E->getKind() == EK_Directory) {
1250       auto *DE = dyn_cast<RedirectingDirectoryEntry>(E);
1251       assert(DE && "Should be a directory");
1252
1253       for (std::unique_ptr<Entry> &SubEntry :
1254            llvm::make_range(DE->contents_begin(), DE->contents_end()))
1255         dumpEntry(SubEntry.get(), NumSpaces + 2);
1256     }
1257   }
1258 #endif
1259 };
1260
1261 /// A helper class to hold the common YAML parsing state.
1262 class RedirectingFileSystemParser {
1263   yaml::Stream &Stream;
1264
1265   void error(yaml::Node *N, const Twine &Msg) { Stream.printError(N, Msg); }
1266
1267   // false on error
1268   bool parseScalarString(yaml::Node *N, StringRef &Result,
1269                          SmallVectorImpl<char> &Storage) {
1270     const auto *S = dyn_cast<yaml::ScalarNode>(N);
1271
1272     if (!S) {
1273       error(N, "expected string");
1274       return false;
1275     }
1276     Result = S->getValue(Storage);
1277     return true;
1278   }
1279
1280   // false on error
1281   bool parseScalarBool(yaml::Node *N, bool &Result) {
1282     SmallString<5> Storage;
1283     StringRef Value;
1284     if (!parseScalarString(N, Value, Storage))
1285       return false;
1286
1287     if (Value.equals_lower("true") || Value.equals_lower("on") ||
1288         Value.equals_lower("yes") || Value == "1") {
1289       Result = true;
1290       return true;
1291     } else if (Value.equals_lower("false") || Value.equals_lower("off") ||
1292                Value.equals_lower("no") || Value == "0") {
1293       Result = false;
1294       return true;
1295     }
1296
1297     error(N, "expected boolean value");
1298     return false;
1299   }
1300
1301   struct KeyStatus {
1302     bool Required;
1303     bool Seen = false;
1304
1305     KeyStatus(bool Required = false) : Required(Required) {}
1306   };
1307
1308   using KeyStatusPair = std::pair<StringRef, KeyStatus>;
1309
1310   // false on error
1311   bool checkDuplicateOrUnknownKey(yaml::Node *KeyNode, StringRef Key,
1312                                   DenseMap<StringRef, KeyStatus> &Keys) {
1313     if (!Keys.count(Key)) {
1314       error(KeyNode, "unknown key");
1315       return false;
1316     }
1317     KeyStatus &S = Keys[Key];
1318     if (S.Seen) {
1319       error(KeyNode, Twine("duplicate key '") + Key + "'");
1320       return false;
1321     }
1322     S.Seen = true;
1323     return true;
1324   }
1325
1326   // false on error
1327   bool checkMissingKeys(yaml::Node *Obj, DenseMap<StringRef, KeyStatus> &Keys) {
1328     for (const auto &I : Keys) {
1329       if (I.second.Required && !I.second.Seen) {
1330         error(Obj, Twine("missing key '") + I.first + "'");
1331         return false;
1332       }
1333     }
1334     return true;
1335   }
1336
1337   Entry *lookupOrCreateEntry(RedirectingFileSystem *FS, StringRef Name,
1338                              Entry *ParentEntry = nullptr) {
1339     if (!ParentEntry) { // Look for a existent root
1340       for (const auto &Root : FS->Roots) {
1341         if (Name.equals(Root->getName())) {
1342           ParentEntry = Root.get();
1343           return ParentEntry;
1344         }
1345       }
1346     } else { // Advance to the next component
1347       auto *DE = dyn_cast<RedirectingDirectoryEntry>(ParentEntry);
1348       for (std::unique_ptr<Entry> &Content :
1349            llvm::make_range(DE->contents_begin(), DE->contents_end())) {
1350         auto *DirContent = dyn_cast<RedirectingDirectoryEntry>(Content.get());
1351         if (DirContent && Name.equals(Content->getName()))
1352           return DirContent;
1353       }
1354     }
1355
1356     // ... or create a new one
1357     std::unique_ptr<Entry> E = llvm::make_unique<RedirectingDirectoryEntry>(
1358         Name,
1359         Status("", getNextVirtualUniqueID(), std::chrono::system_clock::now(),
1360                0, 0, 0, file_type::directory_file, sys::fs::all_all));
1361
1362     if (!ParentEntry) { // Add a new root to the overlay
1363       FS->Roots.push_back(std::move(E));
1364       ParentEntry = FS->Roots.back().get();
1365       return ParentEntry;
1366     }
1367
1368     auto *DE = dyn_cast<RedirectingDirectoryEntry>(ParentEntry);
1369     DE->addContent(std::move(E));
1370     return DE->getLastContent();
1371   }
1372
1373   void uniqueOverlayTree(RedirectingFileSystem *FS, Entry *SrcE,
1374                          Entry *NewParentE = nullptr) {
1375     StringRef Name = SrcE->getName();
1376     switch (SrcE->getKind()) {
1377     case EK_Directory: {
1378       auto *DE = dyn_cast<RedirectingDirectoryEntry>(SrcE);
1379       assert(DE && "Must be a directory");
1380       // Empty directories could be present in the YAML as a way to
1381       // describe a file for a current directory after some of its subdir
1382       // is parsed. This only leads to redundant walks, ignore it.
1383       if (!Name.empty())
1384         NewParentE = lookupOrCreateEntry(FS, Name, NewParentE);
1385       for (std::unique_ptr<Entry> &SubEntry :
1386            llvm::make_range(DE->contents_begin(), DE->contents_end()))
1387         uniqueOverlayTree(FS, SubEntry.get(), NewParentE);
1388       break;
1389     }
1390     case EK_File: {
1391       auto *FE = dyn_cast<RedirectingFileEntry>(SrcE);
1392       assert(FE && "Must be a file");
1393       assert(NewParentE && "Parent entry must exist");
1394       auto *DE = dyn_cast<RedirectingDirectoryEntry>(NewParentE);
1395       DE->addContent(llvm::make_unique<RedirectingFileEntry>(
1396           Name, FE->getExternalContentsPath(), FE->getUseName()));
1397       break;
1398     }
1399     }
1400   }
1401
1402   std::unique_ptr<Entry> parseEntry(yaml::Node *N, RedirectingFileSystem *FS,
1403                                     bool IsRootEntry) {
1404     auto *M = dyn_cast<yaml::MappingNode>(N);
1405     if (!M) {
1406       error(N, "expected mapping node for file or directory entry");
1407       return nullptr;
1408     }
1409
1410     KeyStatusPair Fields[] = {
1411         KeyStatusPair("name", true),
1412         KeyStatusPair("type", true),
1413         KeyStatusPair("contents", false),
1414         KeyStatusPair("external-contents", false),
1415         KeyStatusPair("use-external-name", false),
1416     };
1417
1418     DenseMap<StringRef, KeyStatus> Keys(std::begin(Fields), std::end(Fields));
1419
1420     bool HasContents = false; // external or otherwise
1421     std::vector<std::unique_ptr<Entry>> EntryArrayContents;
1422     std::string ExternalContentsPath;
1423     std::string Name;
1424     yaml::Node *NameValueNode;
1425     auto UseExternalName = RedirectingFileEntry::NK_NotSet;
1426     EntryKind Kind;
1427
1428     for (auto &I : *M) {
1429       StringRef Key;
1430       // Reuse the buffer for key and value, since we don't look at key after
1431       // parsing value.
1432       SmallString<256> Buffer;
1433       if (!parseScalarString(I.getKey(), Key, Buffer))
1434         return nullptr;
1435
1436       if (!checkDuplicateOrUnknownKey(I.getKey(), Key, Keys))
1437         return nullptr;
1438
1439       StringRef Value;
1440       if (Key == "name") {
1441         if (!parseScalarString(I.getValue(), Value, Buffer))
1442           return nullptr;
1443
1444         NameValueNode = I.getValue();
1445         if (FS->UseCanonicalizedPaths) {
1446           SmallString<256> Path(Value);
1447           // Guarantee that old YAML files containing paths with ".." and "."
1448           // are properly canonicalized before read into the VFS.
1449           Path = sys::path::remove_leading_dotslash(Path);
1450           sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
1451           Name = Path.str();
1452         } else {
1453           Name = Value;
1454         }
1455       } else if (Key == "type") {
1456         if (!parseScalarString(I.getValue(), Value, Buffer))
1457           return nullptr;
1458         if (Value == "file")
1459           Kind = EK_File;
1460         else if (Value == "directory")
1461           Kind = EK_Directory;
1462         else {
1463           error(I.getValue(), "unknown value for 'type'");
1464           return nullptr;
1465         }
1466       } else if (Key == "contents") {
1467         if (HasContents) {
1468           error(I.getKey(),
1469                 "entry already has 'contents' or 'external-contents'");
1470           return nullptr;
1471         }
1472         HasContents = true;
1473         auto *Contents = dyn_cast<yaml::SequenceNode>(I.getValue());
1474         if (!Contents) {
1475           // FIXME: this is only for directories, what about files?
1476           error(I.getValue(), "expected array");
1477           return nullptr;
1478         }
1479
1480         for (auto &I : *Contents) {
1481           if (std::unique_ptr<Entry> E =
1482                   parseEntry(&I, FS, /*IsRootEntry*/ false))
1483             EntryArrayContents.push_back(std::move(E));
1484           else
1485             return nullptr;
1486         }
1487       } else if (Key == "external-contents") {
1488         if (HasContents) {
1489           error(I.getKey(),
1490                 "entry already has 'contents' or 'external-contents'");
1491           return nullptr;
1492         }
1493         HasContents = true;
1494         if (!parseScalarString(I.getValue(), Value, Buffer))
1495           return nullptr;
1496
1497         SmallString<256> FullPath;
1498         if (FS->IsRelativeOverlay) {
1499           FullPath = FS->getExternalContentsPrefixDir();
1500           assert(!FullPath.empty() &&
1501                  "External contents prefix directory must exist");
1502           llvm::sys::path::append(FullPath, Value);
1503         } else {
1504           FullPath = Value;
1505         }
1506
1507         if (FS->UseCanonicalizedPaths) {
1508           // Guarantee that old YAML files containing paths with ".." and "."
1509           // are properly canonicalized before read into the VFS.
1510           FullPath = sys::path::remove_leading_dotslash(FullPath);
1511           sys::path::remove_dots(FullPath, /*remove_dot_dot=*/true);
1512         }
1513         ExternalContentsPath = FullPath.str();
1514       } else if (Key == "use-external-name") {
1515         bool Val;
1516         if (!parseScalarBool(I.getValue(), Val))
1517           return nullptr;
1518         UseExternalName = Val ? RedirectingFileEntry::NK_External
1519                               : RedirectingFileEntry::NK_Virtual;
1520       } else {
1521         llvm_unreachable("key missing from Keys");
1522       }
1523     }
1524
1525     if (Stream.failed())
1526       return nullptr;
1527
1528     // check for missing keys
1529     if (!HasContents) {
1530       error(N, "missing key 'contents' or 'external-contents'");
1531       return nullptr;
1532     }
1533     if (!checkMissingKeys(N, Keys))
1534       return nullptr;
1535
1536     // check invalid configuration
1537     if (Kind == EK_Directory &&
1538         UseExternalName != RedirectingFileEntry::NK_NotSet) {
1539       error(N, "'use-external-name' is not supported for directories");
1540       return nullptr;
1541     }
1542
1543     if (IsRootEntry && !sys::path::is_absolute(Name)) {
1544       assert(NameValueNode && "Name presence should be checked earlier");
1545       error(NameValueNode,
1546             "entry with relative path at the root level is not discoverable");
1547       return nullptr;
1548     }
1549
1550     // Remove trailing slash(es), being careful not to remove the root path
1551     StringRef Trimmed(Name);
1552     size_t RootPathLen = sys::path::root_path(Trimmed).size();
1553     while (Trimmed.size() > RootPathLen &&
1554            sys::path::is_separator(Trimmed.back()))
1555       Trimmed = Trimmed.slice(0, Trimmed.size() - 1);
1556     // Get the last component
1557     StringRef LastComponent = sys::path::filename(Trimmed);
1558
1559     std::unique_ptr<Entry> Result;
1560     switch (Kind) {
1561     case EK_File:
1562       Result = llvm::make_unique<RedirectingFileEntry>(
1563           LastComponent, std::move(ExternalContentsPath), UseExternalName);
1564       break;
1565     case EK_Directory:
1566       Result = llvm::make_unique<RedirectingDirectoryEntry>(
1567           LastComponent, std::move(EntryArrayContents),
1568           Status("", getNextVirtualUniqueID(), std::chrono::system_clock::now(),
1569                  0, 0, 0, file_type::directory_file, sys::fs::all_all));
1570       break;
1571     }
1572
1573     StringRef Parent = sys::path::parent_path(Trimmed);
1574     if (Parent.empty())
1575       return Result;
1576
1577     // if 'name' contains multiple components, create implicit directory entries
1578     for (sys::path::reverse_iterator I = sys::path::rbegin(Parent),
1579                                      E = sys::path::rend(Parent);
1580          I != E; ++I) {
1581       std::vector<std::unique_ptr<Entry>> Entries;
1582       Entries.push_back(std::move(Result));
1583       Result = llvm::make_unique<RedirectingDirectoryEntry>(
1584           *I, std::move(Entries),
1585           Status("", getNextVirtualUniqueID(), std::chrono::system_clock::now(),
1586                  0, 0, 0, file_type::directory_file, sys::fs::all_all));
1587     }
1588     return Result;
1589   }
1590
1591 public:
1592   RedirectingFileSystemParser(yaml::Stream &S) : Stream(S) {}
1593
1594   // false on error
1595   bool parse(yaml::Node *Root, RedirectingFileSystem *FS) {
1596     auto *Top = dyn_cast<yaml::MappingNode>(Root);
1597     if (!Top) {
1598       error(Root, "expected mapping node");
1599       return false;
1600     }
1601
1602     KeyStatusPair Fields[] = {
1603         KeyStatusPair("version", true),
1604         KeyStatusPair("case-sensitive", false),
1605         KeyStatusPair("use-external-names", false),
1606         KeyStatusPair("overlay-relative", false),
1607         KeyStatusPair("fallthrough", false),
1608         KeyStatusPair("roots", true),
1609     };
1610
1611     DenseMap<StringRef, KeyStatus> Keys(std::begin(Fields), std::end(Fields));
1612     std::vector<std::unique_ptr<Entry>> RootEntries;
1613
1614     // Parse configuration and 'roots'
1615     for (auto &I : *Top) {
1616       SmallString<10> KeyBuffer;
1617       StringRef Key;
1618       if (!parseScalarString(I.getKey(), Key, KeyBuffer))
1619         return false;
1620
1621       if (!checkDuplicateOrUnknownKey(I.getKey(), Key, Keys))
1622         return false;
1623
1624       if (Key == "roots") {
1625         auto *Roots = dyn_cast<yaml::SequenceNode>(I.getValue());
1626         if (!Roots) {
1627           error(I.getValue(), "expected array");
1628           return false;
1629         }
1630
1631         for (auto &I : *Roots) {
1632           if (std::unique_ptr<Entry> E =
1633                   parseEntry(&I, FS, /*IsRootEntry*/ true))
1634             RootEntries.push_back(std::move(E));
1635           else
1636             return false;
1637         }
1638       } else if (Key == "version") {
1639         StringRef VersionString;
1640         SmallString<4> Storage;
1641         if (!parseScalarString(I.getValue(), VersionString, Storage))
1642           return false;
1643         int Version;
1644         if (VersionString.getAsInteger<int>(10, Version)) {
1645           error(I.getValue(), "expected integer");
1646           return false;
1647         }
1648         if (Version < 0) {
1649           error(I.getValue(), "invalid version number");
1650           return false;
1651         }
1652         if (Version != 0) {
1653           error(I.getValue(), "version mismatch, expected 0");
1654           return false;
1655         }
1656       } else if (Key == "case-sensitive") {
1657         if (!parseScalarBool(I.getValue(), FS->CaseSensitive))
1658           return false;
1659       } else if (Key == "overlay-relative") {
1660         if (!parseScalarBool(I.getValue(), FS->IsRelativeOverlay))
1661           return false;
1662       } else if (Key == "use-external-names") {
1663         if (!parseScalarBool(I.getValue(), FS->UseExternalNames))
1664           return false;
1665       } else if (Key == "fallthrough") {
1666         if (!parseScalarBool(I.getValue(), FS->IsFallthrough))
1667           return false;
1668       } else {
1669         llvm_unreachable("key missing from Keys");
1670       }
1671     }
1672
1673     if (Stream.failed())
1674       return false;
1675
1676     if (!checkMissingKeys(Top, Keys))
1677       return false;
1678
1679     // Now that we sucessefully parsed the YAML file, canonicalize the internal
1680     // representation to a proper directory tree so that we can search faster
1681     // inside the VFS.
1682     for (auto &E : RootEntries)
1683       uniqueOverlayTree(FS, E.get());
1684
1685     return true;
1686   }
1687 };
1688
1689 } // namespace
1690
1691 RedirectingFileSystem *
1692 RedirectingFileSystem::create(std::unique_ptr<MemoryBuffer> Buffer,
1693                               SourceMgr::DiagHandlerTy DiagHandler,
1694                               StringRef YAMLFilePath, void *DiagContext,
1695                               IntrusiveRefCntPtr<FileSystem> ExternalFS) {
1696   SourceMgr SM;
1697   yaml::Stream Stream(Buffer->getMemBufferRef(), SM);
1698
1699   SM.setDiagHandler(DiagHandler, DiagContext);
1700   yaml::document_iterator DI = Stream.begin();
1701   yaml::Node *Root = DI->getRoot();
1702   if (DI == Stream.end() || !Root) {
1703     SM.PrintMessage(SMLoc(), SourceMgr::DK_Error, "expected root node");
1704     return nullptr;
1705   }
1706
1707   RedirectingFileSystemParser P(Stream);
1708
1709   std::unique_ptr<RedirectingFileSystem> FS(
1710       new RedirectingFileSystem(std::move(ExternalFS)));
1711
1712   if (!YAMLFilePath.empty()) {
1713     // Use the YAML path from -ivfsoverlay to compute the dir to be prefixed
1714     // to each 'external-contents' path.
1715     //
1716     // Example:
1717     //    -ivfsoverlay dummy.cache/vfs/vfs.yaml
1718     // yields:
1719     //  FS->ExternalContentsPrefixDir => /<absolute_path_to>/dummy.cache/vfs
1720     //
1721     SmallString<256> OverlayAbsDir = sys::path::parent_path(YAMLFilePath);
1722     std::error_code EC = llvm::sys::fs::make_absolute(OverlayAbsDir);
1723     assert(!EC && "Overlay dir final path must be absolute");
1724     (void)EC;
1725     FS->setExternalContentsPrefixDir(OverlayAbsDir);
1726   }
1727
1728   if (!P.parse(Root, FS.get()))
1729     return nullptr;
1730
1731   return FS.release();
1732 }
1733
1734 ErrorOr<Entry *> RedirectingFileSystem::lookupPath(const Twine &Path_) const {
1735   SmallString<256> Path;
1736   Path_.toVector(Path);
1737
1738   // Handle relative paths
1739   if (std::error_code EC = makeAbsolute(Path))
1740     return EC;
1741
1742   // Canonicalize path by removing ".", "..", "./", etc components. This is
1743   // a VFS request, do bot bother about symlinks in the path components
1744   // but canonicalize in order to perform the correct entry search.
1745   if (UseCanonicalizedPaths) {
1746     Path = sys::path::remove_leading_dotslash(Path);
1747     sys::path::remove_dots(Path, /*remove_dot_dot=*/true);
1748   }
1749
1750   if (Path.empty())
1751     return make_error_code(llvm::errc::invalid_argument);
1752
1753   sys::path::const_iterator Start = sys::path::begin(Path);
1754   sys::path::const_iterator End = sys::path::end(Path);
1755   for (const auto &Root : Roots) {
1756     ErrorOr<Entry *> Result = lookupPath(Start, End, Root.get());
1757     if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
1758       return Result;
1759   }
1760   return make_error_code(llvm::errc::no_such_file_or_directory);
1761 }
1762
1763 ErrorOr<Entry *>
1764 RedirectingFileSystem::lookupPath(sys::path::const_iterator Start,
1765                                   sys::path::const_iterator End,
1766                                   Entry *From) const {
1767 #ifndef _WIN32
1768   assert(!isTraversalComponent(*Start) &&
1769          !isTraversalComponent(From->getName()) &&
1770          "Paths should not contain traversal components");
1771 #else
1772   // FIXME: this is here to support windows, remove it once canonicalized
1773   // paths become globally default.
1774   if (Start->equals("."))
1775     ++Start;
1776 #endif
1777
1778   StringRef FromName = From->getName();
1779
1780   // Forward the search to the next component in case this is an empty one.
1781   if (!FromName.empty()) {
1782     if (CaseSensitive ? !Start->equals(FromName)
1783                       : !Start->equals_lower(FromName))
1784       // failure to match
1785       return make_error_code(llvm::errc::no_such_file_or_directory);
1786
1787     ++Start;
1788
1789     if (Start == End) {
1790       // Match!
1791       return From;
1792     }
1793   }
1794
1795   auto *DE = dyn_cast<RedirectingDirectoryEntry>(From);
1796   if (!DE)
1797     return make_error_code(llvm::errc::not_a_directory);
1798
1799   for (const std::unique_ptr<Entry> &DirEntry :
1800        llvm::make_range(DE->contents_begin(), DE->contents_end())) {
1801     ErrorOr<Entry *> Result = lookupPath(Start, End, DirEntry.get());
1802     if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
1803       return Result;
1804   }
1805   return make_error_code(llvm::errc::no_such_file_or_directory);
1806 }
1807
1808 static Status getRedirectedFileStatus(const Twine &Path, bool UseExternalNames,
1809                                       Status ExternalStatus) {
1810   Status S = ExternalStatus;
1811   if (!UseExternalNames)
1812     S = Status::copyWithNewName(S, Path.str());
1813   S.IsVFSMapped = true;
1814   return S;
1815 }
1816
1817 ErrorOr<Status> RedirectingFileSystem::status(const Twine &Path, Entry *E) {
1818   assert(E != nullptr);
1819   if (auto *F = dyn_cast<RedirectingFileEntry>(E)) {
1820     ErrorOr<Status> S = ExternalFS->status(F->getExternalContentsPath());
1821     assert(!S || S->getName() == F->getExternalContentsPath());
1822     if (S)
1823       return getRedirectedFileStatus(Path, F->useExternalName(UseExternalNames),
1824                                      *S);
1825     return S;
1826   } else { // directory
1827     auto *DE = cast<RedirectingDirectoryEntry>(E);
1828     return Status::copyWithNewName(DE->getStatus(), Path.str());
1829   }
1830 }
1831
1832 ErrorOr<Status> RedirectingFileSystem::status(const Twine &Path) {
1833   ErrorOr<Entry *> Result = lookupPath(Path);
1834   if (!Result) {
1835     if (IsFallthrough &&
1836         Result.getError() == llvm::errc::no_such_file_or_directory) {
1837       return ExternalFS->status(Path);
1838     }
1839     return Result.getError();
1840   }
1841   return status(Path, *Result);
1842 }
1843
1844 namespace {
1845
1846 /// Provide a file wrapper with an overriden status.
1847 class FileWithFixedStatus : public File {
1848   std::unique_ptr<File> InnerFile;
1849   Status S;
1850
1851 public:
1852   FileWithFixedStatus(std::unique_ptr<File> InnerFile, Status S)
1853       : InnerFile(std::move(InnerFile)), S(std::move(S)) {}
1854
1855   ErrorOr<Status> status() override { return S; }
1856   ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>
1857
1858   getBuffer(const Twine &Name, int64_t FileSize, bool RequiresNullTerminator,
1859             bool IsVolatile) override {
1860     return InnerFile->getBuffer(Name, FileSize, RequiresNullTerminator,
1861                                 IsVolatile);
1862   }
1863
1864   std::error_code close() override { return InnerFile->close(); }
1865 };
1866
1867 } // namespace
1868
1869 ErrorOr<std::unique_ptr<File>>
1870 RedirectingFileSystem::openFileForRead(const Twine &Path) {
1871   ErrorOr<Entry *> E = lookupPath(Path);
1872   if (!E) {
1873     if (IsFallthrough &&
1874         E.getError() == llvm::errc::no_such_file_or_directory) {
1875       return ExternalFS->openFileForRead(Path);
1876     }
1877     return E.getError();
1878   }
1879
1880   auto *F = dyn_cast<RedirectingFileEntry>(*E);
1881   if (!F) // FIXME: errc::not_a_file?
1882     return make_error_code(llvm::errc::invalid_argument);
1883
1884   auto Result = ExternalFS->openFileForRead(F->getExternalContentsPath());
1885   if (!Result)
1886     return Result;
1887
1888   auto ExternalStatus = (*Result)->status();
1889   if (!ExternalStatus)
1890     return ExternalStatus.getError();
1891
1892   // FIXME: Update the status with the name and VFSMapped.
1893   Status S = getRedirectedFileStatus(Path, F->useExternalName(UseExternalNames),
1894                                      *ExternalStatus);
1895   return std::unique_ptr<File>(
1896       llvm::make_unique<FileWithFixedStatus>(std::move(*Result), S));
1897 }
1898
1899 std::error_code
1900 RedirectingFileSystem::getRealPath(const Twine &Path,
1901                                    SmallVectorImpl<char> &Output) const {
1902   ErrorOr<Entry *> Result = lookupPath(Path);
1903   if (!Result) {
1904     if (IsFallthrough &&
1905         Result.getError() == llvm::errc::no_such_file_or_directory) {
1906       return ExternalFS->getRealPath(Path, Output);
1907     }
1908     return Result.getError();
1909   }
1910
1911   if (auto *F = dyn_cast<RedirectingFileEntry>(*Result)) {
1912     return ExternalFS->getRealPath(F->getExternalContentsPath(), Output);
1913   }
1914   // Even if there is a directory entry, fall back to ExternalFS if allowed,
1915   // because directories don't have a single external contents path.
1916   return IsFallthrough ? ExternalFS->getRealPath(Path, Output)
1917                        : llvm::errc::invalid_argument;
1918 }
1919
1920 IntrusiveRefCntPtr<FileSystem>
1921 vfs::getVFSFromYAML(std::unique_ptr<MemoryBuffer> Buffer,
1922                     SourceMgr::DiagHandlerTy DiagHandler,
1923                     StringRef YAMLFilePath, void *DiagContext,
1924                     IntrusiveRefCntPtr<FileSystem> ExternalFS) {
1925   return RedirectingFileSystem::create(std::move(Buffer), DiagHandler,
1926                                        YAMLFilePath, DiagContext,
1927                                        std::move(ExternalFS));
1928 }
1929
1930 static void getVFSEntries(Entry *SrcE, SmallVectorImpl<StringRef> &Path,
1931                           SmallVectorImpl<YAMLVFSEntry> &Entries) {
1932   auto Kind = SrcE->getKind();
1933   if (Kind == EK_Directory) {
1934     auto *DE = dyn_cast<RedirectingDirectoryEntry>(SrcE);
1935     assert(DE && "Must be a directory");
1936     for (std::unique_ptr<Entry> &SubEntry :
1937          llvm::make_range(DE->contents_begin(), DE->contents_end())) {
1938       Path.push_back(SubEntry->getName());
1939       getVFSEntries(SubEntry.get(), Path, Entries);
1940       Path.pop_back();
1941     }
1942     return;
1943   }
1944
1945   assert(Kind == EK_File && "Must be a EK_File");
1946   auto *FE = dyn_cast<RedirectingFileEntry>(SrcE);
1947   assert(FE && "Must be a file");
1948   SmallString<128> VPath;
1949   for (auto &Comp : Path)
1950     llvm::sys::path::append(VPath, Comp);
1951   Entries.push_back(YAMLVFSEntry(VPath.c_str(), FE->getExternalContentsPath()));
1952 }
1953
1954 void vfs::collectVFSFromYAML(std::unique_ptr<MemoryBuffer> Buffer,
1955                              SourceMgr::DiagHandlerTy DiagHandler,
1956                              StringRef YAMLFilePath,
1957                              SmallVectorImpl<YAMLVFSEntry> &CollectedEntries,
1958                              void *DiagContext,
1959                              IntrusiveRefCntPtr<FileSystem> ExternalFS) {
1960   RedirectingFileSystem *VFS = RedirectingFileSystem::create(
1961       std::move(Buffer), DiagHandler, YAMLFilePath, DiagContext,
1962       std::move(ExternalFS));
1963   ErrorOr<Entry *> RootE = VFS->lookupPath("/");
1964   if (!RootE)
1965     return;
1966   SmallVector<StringRef, 8> Components;
1967   Components.push_back("/");
1968   getVFSEntries(*RootE, Components, CollectedEntries);
1969 }
1970
1971 UniqueID vfs::getNextVirtualUniqueID() {
1972   static std::atomic<unsigned> UID;
1973   unsigned ID = ++UID;
1974   // The following assumes that uint64_t max will never collide with a real
1975   // dev_t value from the OS.
1976   return UniqueID(std::numeric_limits<uint64_t>::max(), ID);
1977 }
1978
1979 void YAMLVFSWriter::addFileMapping(StringRef VirtualPath, StringRef RealPath) {
1980   assert(sys::path::is_absolute(VirtualPath) && "virtual path not absolute");
1981   assert(sys::path::is_absolute(RealPath) && "real path not absolute");
1982   assert(!pathHasTraversal(VirtualPath) && "path traversal is not supported");
1983   Mappings.emplace_back(VirtualPath, RealPath);
1984 }
1985
1986 namespace {
1987
1988 class JSONWriter {
1989   llvm::raw_ostream &OS;
1990   SmallVector<StringRef, 16> DirStack;
1991
1992   unsigned getDirIndent() { return 4 * DirStack.size(); }
1993   unsigned getFileIndent() { return 4 * (DirStack.size() + 1); }
1994   bool containedIn(StringRef Parent, StringRef Path);
1995   StringRef containedPart(StringRef Parent, StringRef Path);
1996   void startDirectory(StringRef Path);
1997   void endDirectory();
1998   void writeEntry(StringRef VPath, StringRef RPath);
1999
2000 public:
2001   JSONWriter(llvm::raw_ostream &OS) : OS(OS) {}
2002
2003   void write(ArrayRef<YAMLVFSEntry> Entries, Optional<bool> UseExternalNames,
2004              Optional<bool> IsCaseSensitive, Optional<bool> IsOverlayRelative,
2005              StringRef OverlayDir);
2006 };
2007
2008 } // namespace
2009
2010 bool JSONWriter::containedIn(StringRef Parent, StringRef Path) {
2011   using namespace llvm::sys;
2012
2013   // Compare each path component.
2014   auto IParent = path::begin(Parent), EParent = path::end(Parent);
2015   for (auto IChild = path::begin(Path), EChild = path::end(Path);
2016        IParent != EParent && IChild != EChild; ++IParent, ++IChild) {
2017     if (*IParent != *IChild)
2018       return false;
2019   }
2020   // Have we exhausted the parent path?
2021   return IParent == EParent;
2022 }
2023
2024 StringRef JSONWriter::containedPart(StringRef Parent, StringRef Path) {
2025   assert(!Parent.empty());
2026   assert(containedIn(Parent, Path));
2027   return Path.slice(Parent.size() + 1, StringRef::npos);
2028 }
2029
2030 void JSONWriter::startDirectory(StringRef Path) {
2031   StringRef Name =
2032       DirStack.empty() ? Path : containedPart(DirStack.back(), Path);
2033   DirStack.push_back(Path);
2034   unsigned Indent = getDirIndent();
2035   OS.indent(Indent) << "{\n";
2036   OS.indent(Indent + 2) << "'type': 'directory',\n";
2037   OS.indent(Indent + 2) << "'name': \"" << llvm::yaml::escape(Name) << "\",\n";
2038   OS.indent(Indent + 2) << "'contents': [\n";
2039 }
2040
2041 void JSONWriter::endDirectory() {
2042   unsigned Indent = getDirIndent();
2043   OS.indent(Indent + 2) << "]\n";
2044   OS.indent(Indent) << "}";
2045
2046   DirStack.pop_back();
2047 }
2048
2049 void JSONWriter::writeEntry(StringRef VPath, StringRef RPath) {
2050   unsigned Indent = getFileIndent();
2051   OS.indent(Indent) << "{\n";
2052   OS.indent(Indent + 2) << "'type': 'file',\n";
2053   OS.indent(Indent + 2) << "'name': \"" << llvm::yaml::escape(VPath) << "\",\n";
2054   OS.indent(Indent + 2) << "'external-contents': \""
2055                         << llvm::yaml::escape(RPath) << "\"\n";
2056   OS.indent(Indent) << "}";
2057 }
2058
2059 void JSONWriter::write(ArrayRef<YAMLVFSEntry> Entries,
2060                        Optional<bool> UseExternalNames,
2061                        Optional<bool> IsCaseSensitive,
2062                        Optional<bool> IsOverlayRelative,
2063                        StringRef OverlayDir) {
2064   using namespace llvm::sys;
2065
2066   OS << "{\n"
2067         "  'version': 0,\n";
2068   if (IsCaseSensitive.hasValue())
2069     OS << "  'case-sensitive': '"
2070        << (IsCaseSensitive.getValue() ? "true" : "false") << "',\n";
2071   if (UseExternalNames.hasValue())
2072     OS << "  'use-external-names': '"
2073        << (UseExternalNames.getValue() ? "true" : "false") << "',\n";
2074   bool UseOverlayRelative = false;
2075   if (IsOverlayRelative.hasValue()) {
2076     UseOverlayRelative = IsOverlayRelative.getValue();
2077     OS << "  'overlay-relative': '" << (UseOverlayRelative ? "true" : "false")
2078        << "',\n";
2079   }
2080   OS << "  'roots': [\n";
2081
2082   if (!Entries.empty()) {
2083     const YAMLVFSEntry &Entry = Entries.front();
2084     startDirectory(path::parent_path(Entry.VPath));
2085
2086     StringRef RPath = Entry.RPath;
2087     if (UseOverlayRelative) {
2088       unsigned OverlayDirLen = OverlayDir.size();
2089       assert(RPath.substr(0, OverlayDirLen) == OverlayDir &&
2090              "Overlay dir must be contained in RPath");
2091       RPath = RPath.slice(OverlayDirLen, RPath.size());
2092     }
2093
2094     writeEntry(path::filename(Entry.VPath), RPath);
2095
2096     for (const auto &Entry : Entries.slice(1)) {
2097       StringRef Dir = path::parent_path(Entry.VPath);
2098       if (Dir == DirStack.back())
2099         OS << ",\n";
2100       else {
2101         while (!DirStack.empty() && !containedIn(DirStack.back(), Dir)) {
2102           OS << "\n";
2103           endDirectory();
2104         }
2105         OS << ",\n";
2106         startDirectory(Dir);
2107       }
2108       StringRef RPath = Entry.RPath;
2109       if (UseOverlayRelative) {
2110         unsigned OverlayDirLen = OverlayDir.size();
2111         assert(RPath.substr(0, OverlayDirLen) == OverlayDir &&
2112                "Overlay dir must be contained in RPath");
2113         RPath = RPath.slice(OverlayDirLen, RPath.size());
2114       }
2115       writeEntry(path::filename(Entry.VPath), RPath);
2116     }
2117
2118     while (!DirStack.empty()) {
2119       OS << "\n";
2120       endDirectory();
2121     }
2122     OS << "\n";
2123   }
2124
2125   OS << "  ]\n"
2126      << "}\n";
2127 }
2128
2129 void YAMLVFSWriter::write(llvm::raw_ostream &OS) {
2130   llvm::sort(Mappings, [](const YAMLVFSEntry &LHS, const YAMLVFSEntry &RHS) {
2131     return LHS.VPath < RHS.VPath;
2132   });
2133
2134   JSONWriter(OS).write(Mappings, UseExternalNames, IsCaseSensitive,
2135                        IsOverlayRelative, OverlayDir);
2136 }
2137
2138 VFSFromYamlDirIterImpl::VFSFromYamlDirIterImpl(
2139     const Twine &_Path, RedirectingDirectoryEntry::iterator Begin,
2140     RedirectingDirectoryEntry::iterator End, bool IterateExternalFS,
2141     FileSystem &ExternalFS, std::error_code &EC)
2142     : Dir(_Path.str()), Current(Begin), End(End),
2143       IterateExternalFS(IterateExternalFS), ExternalFS(ExternalFS) {
2144   EC = incrementImpl(/*IsFirstTime=*/true);
2145 }
2146
2147 std::error_code VFSFromYamlDirIterImpl::increment() {
2148   return incrementImpl(/*IsFirstTime=*/false);
2149 }
2150
2151 std::error_code VFSFromYamlDirIterImpl::incrementExternal() {
2152   assert(!(IsExternalFSCurrent && ExternalDirIter == directory_iterator()) &&
2153          "incrementing past end");
2154   std::error_code EC;
2155   if (IsExternalFSCurrent) {
2156     ExternalDirIter.increment(EC);
2157   } else if (IterateExternalFS) {
2158     ExternalDirIter = ExternalFS.dir_begin(Dir, EC);
2159     IsExternalFSCurrent = true;
2160     if (EC && EC != errc::no_such_file_or_directory)
2161       return EC;
2162     EC = {};
2163   }
2164   if (EC || ExternalDirIter == directory_iterator()) {
2165     CurrentEntry = directory_entry();
2166   } else {
2167     CurrentEntry = *ExternalDirIter;
2168   }
2169   return EC;
2170 }
2171
2172 std::error_code VFSFromYamlDirIterImpl::incrementContent(bool IsFirstTime) {
2173   assert((IsFirstTime || Current != End) && "cannot iterate past end");
2174   if (!IsFirstTime)
2175     ++Current;
2176   while (Current != End) {
2177     SmallString<128> PathStr(Dir);
2178     llvm::sys::path::append(PathStr, (*Current)->getName());
2179     sys::fs::file_type Type;
2180     switch ((*Current)->getKind()) {
2181     case EK_Directory:
2182       Type = sys::fs::file_type::directory_file;
2183       break;
2184     case EK_File:
2185       Type = sys::fs::file_type::regular_file;
2186       break;
2187     }
2188     CurrentEntry = directory_entry(PathStr.str(), Type);
2189     return {};
2190   }
2191   return incrementExternal();
2192 }
2193
2194 std::error_code VFSFromYamlDirIterImpl::incrementImpl(bool IsFirstTime) {
2195   while (true) {
2196     std::error_code EC = IsExternalFSCurrent ? incrementExternal()
2197                                              : incrementContent(IsFirstTime);
2198     if (EC || CurrentEntry.path().empty())
2199       return EC;
2200     StringRef Name = llvm::sys::path::filename(CurrentEntry.path());
2201     if (SeenNames.insert(Name).second)
2202       return EC; // name not seen before
2203   }
2204   llvm_unreachable("returned above");
2205 }
2206
2207 vfs::recursive_directory_iterator::recursive_directory_iterator(
2208     FileSystem &FS_, const Twine &Path, std::error_code &EC)
2209     : FS(&FS_) {
2210   directory_iterator I = FS->dir_begin(Path, EC);
2211   if (I != directory_iterator()) {
2212     State = std::make_shared<detail::RecDirIterState>();
2213     State->Stack.push(I);
2214   }
2215 }
2216
2217 vfs::recursive_directory_iterator &
2218 recursive_directory_iterator::increment(std::error_code &EC) {
2219   assert(FS && State && !State->Stack.empty() && "incrementing past end");
2220   assert(!State->Stack.top()->path().empty() && "non-canonical end iterator");
2221   vfs::directory_iterator End;
2222
2223   if (State->HasNoPushRequest)
2224     State->HasNoPushRequest = false;
2225   else {
2226     if (State->Stack.top()->type() == sys::fs::file_type::directory_file) {
2227       vfs::directory_iterator I = FS->dir_begin(State->Stack.top()->path(), EC);
2228       if (I != End) {
2229         State->Stack.push(I);
2230         return *this;
2231       }
2232     }
2233   }
2234
2235   while (!State->Stack.empty() && State->Stack.top().increment(EC) == End)
2236     State->Stack.pop();
2237
2238   if (State->Stack.empty())
2239     State.reset(); // end iterator
2240
2241   return *this;
2242 }