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