contrib/llvm/tools/clang/lib/Basic/VirtualFileSystem.cpp

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