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