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