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 "llvm/ADT/DenseMap.h"
14#include "llvm/ADT/iterator_range.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/StringExtras.h"
17#include "llvm/ADT/StringSet.h"
18#include "llvm/Support/Errc.h"
19#include "llvm/Support/MemoryBuffer.h"
20#include "llvm/Support/Path.h"
21#include "llvm/Support/YAMLParser.h"
22#include <atomic>
23#include <memory>
24
25using namespace clang;
26using namespace clang::vfs;
27using namespace llvm;
28using llvm::sys::fs::file_status;
29using llvm::sys::fs::file_type;
30using llvm::sys::fs::perms;
31using llvm::sys::fs::UniqueID;
32
33Status::Status(const file_status &Status)
34    : UID(Status.getUniqueID()), MTime(Status.getLastModificationTime()),
35      User(Status.getUser()), Group(Status.getGroup()), Size(Status.getSize()),
36      Type(Status.type()), Perms(Status.permissions()), IsVFSMapped(false)  {}
37
38Status::Status(StringRef Name, StringRef ExternalName, UniqueID UID,
39               sys::TimeValue MTime, uint32_t User, uint32_t Group,
40               uint64_t Size, file_type Type, perms Perms)
41    : Name(Name), UID(UID), MTime(MTime), User(User), Group(Group), Size(Size),
42      Type(Type), Perms(Perms), IsVFSMapped(false) {}
43
44bool Status::equivalent(const Status &Other) const {
45  return getUniqueID() == Other.getUniqueID();
46}
47bool Status::isDirectory() const {
48  return Type == file_type::directory_file;
49}
50bool Status::isRegularFile() const {
51  return Type == file_type::regular_file;
52}
53bool Status::isOther() const {
54  return exists() && !isRegularFile() && !isDirectory() && !isSymlink();
55}
56bool Status::isSymlink() const {
57  return Type == file_type::symlink_file;
58}
59bool Status::isStatusKnown() const {
60  return Type != file_type::status_error;
61}
62bool Status::exists() const {
63  return isStatusKnown() && Type != file_type::file_not_found;
64}
65
66File::~File() {}
67
68FileSystem::~FileSystem() {}
69
70std::error_code FileSystem::getBufferForFile(
71    const llvm::Twine &Name, std::unique_ptr<MemoryBuffer> &Result,
72    int64_t FileSize, bool RequiresNullTerminator, bool IsVolatile) {
73  std::unique_ptr<File> F;
74  if (std::error_code EC = openFileForRead(Name, F))
75    return EC;
76
77  std::error_code EC =
78      F->getBuffer(Name, Result, FileSize, RequiresNullTerminator, IsVolatile);
79  return EC;
80}
81
82//===-----------------------------------------------------------------------===/
83// RealFileSystem implementation
84//===-----------------------------------------------------------------------===/
85
86namespace {
87/// \brief Wrapper around a raw file descriptor.
88class RealFile : public File {
89  int FD;
90  Status S;
91  friend class RealFileSystem;
92  RealFile(int FD) : FD(FD) {
93    assert(FD >= 0 && "Invalid or inactive file descriptor");
94  }
95
96public:
97  ~RealFile();
98  ErrorOr<Status> status() override;
99  std::error_code getBuffer(const Twine &Name,
100                            std::unique_ptr<MemoryBuffer> &Result,
101                            int64_t FileSize = -1,
102                            bool RequiresNullTerminator = true,
103                            bool IsVolatile = false) override;
104  std::error_code close() override;
105  void setName(StringRef Name) override;
106};
107} // end anonymous namespace
108RealFile::~RealFile() { close(); }
109
110ErrorOr<Status> RealFile::status() {
111  assert(FD != -1 && "cannot stat closed file");
112  if (!S.isStatusKnown()) {
113    file_status RealStatus;
114    if (std::error_code EC = sys::fs::status(FD, RealStatus))
115      return EC;
116    Status NewS(RealStatus);
117    NewS.setName(S.getName());
118    S = std::move(NewS);
119  }
120  return S;
121}
122
123std::error_code RealFile::getBuffer(const Twine &Name,
124                                    std::unique_ptr<MemoryBuffer> &Result,
125                                    int64_t FileSize,
126                                    bool RequiresNullTerminator,
127                                    bool IsVolatile) {
128  assert(FD != -1 && "cannot get buffer for closed file");
129  ErrorOr<std::unique_ptr<MemoryBuffer>> BufferOrErr =
130      MemoryBuffer::getOpenFile(FD, Name.str().c_str(), FileSize,
131                                RequiresNullTerminator, IsVolatile);
132  if (std::error_code EC = BufferOrErr.getError())
133    return EC;
134  Result = std::move(BufferOrErr.get());
135  return std::error_code();
136}
137
138// FIXME: This is terrible, we need this for ::close.
139#if !defined(_MSC_VER) && !defined(__MINGW32__)
140#include <unistd.h>
141#include <sys/uio.h>
142#else
143#include <io.h>
144#ifndef S_ISFIFO
145#define S_ISFIFO(x) (0)
146#endif
147#endif
148std::error_code RealFile::close() {
149  if (::close(FD))
150    return std::error_code(errno, std::generic_category());
151  FD = -1;
152  return std::error_code();
153}
154
155void RealFile::setName(StringRef Name) {
156  S.setName(Name);
157}
158
159namespace {
160/// \brief The file system according to your operating system.
161class RealFileSystem : public FileSystem {
162public:
163  ErrorOr<Status> status(const Twine &Path) override;
164  std::error_code openFileForRead(const Twine &Path,
165                                  std::unique_ptr<File> &Result) override;
166  directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override;
167};
168} // end anonymous namespace
169
170ErrorOr<Status> RealFileSystem::status(const Twine &Path) {
171  sys::fs::file_status RealStatus;
172  if (std::error_code EC = sys::fs::status(Path, RealStatus))
173    return EC;
174  Status Result(RealStatus);
175  Result.setName(Path.str());
176  return Result;
177}
178
179std::error_code RealFileSystem::openFileForRead(const Twine &Name,
180                                                std::unique_ptr<File> &Result) {
181  int FD;
182  if (std::error_code EC = sys::fs::openFileForRead(Name, FD))
183    return EC;
184  Result.reset(new RealFile(FD));
185  Result->setName(Name.str());
186  return std::error_code();
187}
188
189IntrusiveRefCntPtr<FileSystem> vfs::getRealFileSystem() {
190  static IntrusiveRefCntPtr<FileSystem> FS = new RealFileSystem();
191  return FS;
192}
193
194namespace {
195class RealFSDirIter : public clang::vfs::detail::DirIterImpl {
196  std::string Path;
197  llvm::sys::fs::directory_iterator Iter;
198public:
199  RealFSDirIter(const Twine &_Path, std::error_code &EC)
200      : Path(_Path.str()), Iter(Path, EC) {
201    if (!EC && Iter != llvm::sys::fs::directory_iterator()) {
202      llvm::sys::fs::file_status S;
203      EC = Iter->status(S);
204      if (!EC) {
205        CurrentEntry = Status(S);
206        CurrentEntry.setName(Iter->path());
207      }
208    }
209  }
210
211  std::error_code increment() override {
212    std::error_code EC;
213    Iter.increment(EC);
214    if (EC) {
215      return EC;
216    } else if (Iter == llvm::sys::fs::directory_iterator()) {
217      CurrentEntry = Status();
218    } else {
219      llvm::sys::fs::file_status S;
220      EC = Iter->status(S);
221      CurrentEntry = Status(S);
222      CurrentEntry.setName(Iter->path());
223    }
224    return EC;
225  }
226};
227}
228
229directory_iterator RealFileSystem::dir_begin(const Twine &Dir,
230                                             std::error_code &EC) {
231  return directory_iterator(std::make_shared<RealFSDirIter>(Dir, EC));
232}
233
234//===-----------------------------------------------------------------------===/
235// OverlayFileSystem implementation
236//===-----------------------------------------------------------------------===/
237OverlayFileSystem::OverlayFileSystem(IntrusiveRefCntPtr<FileSystem> BaseFS) {
238  pushOverlay(BaseFS);
239}
240
241void OverlayFileSystem::pushOverlay(IntrusiveRefCntPtr<FileSystem> FS) {
242  FSList.push_back(FS);
243}
244
245ErrorOr<Status> OverlayFileSystem::status(const Twine &Path) {
246  // FIXME: handle symlinks that cross file systems
247  for (iterator I = overlays_begin(), E = overlays_end(); I != E; ++I) {
248    ErrorOr<Status> Status = (*I)->status(Path);
249    if (Status || Status.getError() != llvm::errc::no_such_file_or_directory)
250      return Status;
251  }
252  return make_error_code(llvm::errc::no_such_file_or_directory);
253}
254
255std::error_code
256OverlayFileSystem::openFileForRead(const llvm::Twine &Path,
257                                   std::unique_ptr<File> &Result) {
258  // FIXME: handle symlinks that cross file systems
259  for (iterator I = overlays_begin(), E = overlays_end(); I != E; ++I) {
260    std::error_code EC = (*I)->openFileForRead(Path, Result);
261    if (!EC || EC != llvm::errc::no_such_file_or_directory)
262      return EC;
263  }
264  return make_error_code(llvm::errc::no_such_file_or_directory);
265}
266
267clang::vfs::detail::DirIterImpl::~DirIterImpl() { }
268
269namespace {
270class OverlayFSDirIterImpl : public clang::vfs::detail::DirIterImpl {
271  OverlayFileSystem &Overlays;
272  std::string Path;
273  OverlayFileSystem::iterator CurrentFS;
274  directory_iterator CurrentDirIter;
275  llvm::StringSet<> SeenNames;
276
277  std::error_code incrementFS() {
278    assert(CurrentFS != Overlays.overlays_end() && "incrementing past end");
279    ++CurrentFS;
280    for (auto E = Overlays.overlays_end(); CurrentFS != E; ++CurrentFS) {
281      std::error_code EC;
282      CurrentDirIter = (*CurrentFS)->dir_begin(Path, EC);
283      if (EC && EC != errc::no_such_file_or_directory)
284        return EC;
285      if (CurrentDirIter != directory_iterator())
286        break; // found
287    }
288    return std::error_code();
289  }
290
291  std::error_code incrementDirIter(bool IsFirstTime) {
292    assert((IsFirstTime || CurrentDirIter != directory_iterator()) &&
293           "incrementing past end");
294    std::error_code EC;
295    if (!IsFirstTime)
296      CurrentDirIter.increment(EC);
297    if (!EC && CurrentDirIter == directory_iterator())
298      EC = incrementFS();
299    return EC;
300  }
301
302  std::error_code incrementImpl(bool IsFirstTime) {
303    while (true) {
304      std::error_code EC = incrementDirIter(IsFirstTime);
305      if (EC || CurrentDirIter == directory_iterator()) {
306        CurrentEntry = Status();
307        return EC;
308      }
309      CurrentEntry = *CurrentDirIter;
310      StringRef Name = llvm::sys::path::filename(CurrentEntry.getName());
311      if (SeenNames.insert(Name))
312        return EC; // name not seen before
313    }
314    llvm_unreachable("returned above");
315  }
316
317public:
318  OverlayFSDirIterImpl(const Twine &Path, OverlayFileSystem &FS,
319                       std::error_code &EC)
320      : Overlays(FS), Path(Path.str()), CurrentFS(Overlays.overlays_begin()) {
321    CurrentDirIter = (*CurrentFS)->dir_begin(Path, EC);
322    EC = incrementImpl(true);
323  }
324
325  std::error_code increment() override { return incrementImpl(false); }
326};
327} // end anonymous namespace
328
329directory_iterator OverlayFileSystem::dir_begin(const Twine &Dir,
330                                                std::error_code &EC) {
331  return directory_iterator(
332      std::make_shared<OverlayFSDirIterImpl>(Dir, *this, EC));
333}
334
335//===-----------------------------------------------------------------------===/
336// VFSFromYAML implementation
337//===-----------------------------------------------------------------------===/
338
339// Allow DenseMap<StringRef, ...>.  This is useful below because we know all the
340// strings are literals and will outlive the map, and there is no reason to
341// store them.
342namespace llvm {
343  template<>
344  struct DenseMapInfo<StringRef> {
345    // This assumes that "" will never be a valid key.
346    static inline StringRef getEmptyKey() { return StringRef(""); }
347    static inline StringRef getTombstoneKey() { return StringRef(); }
348    static unsigned getHashValue(StringRef Val) { return HashString(Val); }
349    static bool isEqual(StringRef LHS, StringRef RHS) { return LHS == RHS; }
350  };
351}
352
353namespace {
354
355enum EntryKind {
356  EK_Directory,
357  EK_File
358};
359
360/// \brief A single file or directory in the VFS.
361class Entry {
362  EntryKind Kind;
363  std::string Name;
364
365public:
366  virtual ~Entry();
367  Entry(EntryKind K, StringRef Name) : Kind(K), Name(Name) {}
368  StringRef getName() const { return Name; }
369  EntryKind getKind() const { return Kind; }
370};
371
372class DirectoryEntry : public Entry {
373  std::vector<Entry *> Contents;
374  Status S;
375
376public:
377  virtual ~DirectoryEntry();
378  DirectoryEntry(StringRef Name, std::vector<Entry *> Contents, Status S)
379      : Entry(EK_Directory, Name), Contents(std::move(Contents)),
380        S(std::move(S)) {}
381  Status getStatus() { return S; }
382  typedef std::vector<Entry *>::iterator iterator;
383  iterator contents_begin() { return Contents.begin(); }
384  iterator contents_end() { return Contents.end(); }
385  static bool classof(const Entry *E) { return E->getKind() == EK_Directory; }
386};
387
388class FileEntry : public Entry {
389public:
390  enum NameKind {
391    NK_NotSet,
392    NK_External,
393    NK_Virtual
394  };
395private:
396  std::string ExternalContentsPath;
397  NameKind UseName;
398public:
399  FileEntry(StringRef Name, StringRef ExternalContentsPath, NameKind UseName)
400      : Entry(EK_File, Name), ExternalContentsPath(ExternalContentsPath),
401        UseName(UseName) {}
402  StringRef getExternalContentsPath() const { return ExternalContentsPath; }
403  /// \brief whether to use the external path as the name for this file.
404  bool useExternalName(bool GlobalUseExternalName) const {
405    return UseName == NK_NotSet ? GlobalUseExternalName
406                                : (UseName == NK_External);
407  }
408  static bool classof(const Entry *E) { return E->getKind() == EK_File; }
409};
410
411class VFSFromYAML;
412
413class VFSFromYamlDirIterImpl : public clang::vfs::detail::DirIterImpl {
414  std::string Dir;
415  VFSFromYAML &FS;
416  DirectoryEntry::iterator Current, End;
417public:
418  VFSFromYamlDirIterImpl(const Twine &Path, VFSFromYAML &FS,
419                         DirectoryEntry::iterator Begin,
420                         DirectoryEntry::iterator End, std::error_code &EC);
421  std::error_code increment() override;
422};
423
424/// \brief A virtual file system parsed from a YAML file.
425///
426/// Currently, this class allows creating virtual directories and mapping
427/// virtual file paths to existing external files, available in \c ExternalFS.
428///
429/// The basic structure of the parsed file is:
430/// \verbatim
431/// {
432///   'version': <version number>,
433///   <optional configuration>
434///   'roots': [
435///              <directory entries>
436///            ]
437/// }
438/// \endverbatim
439///
440/// All configuration options are optional.
441///   'case-sensitive': <boolean, default=true>
442///   'use-external-names': <boolean, default=true>
443///
444/// Virtual directories are represented as
445/// \verbatim
446/// {
447///   'type': 'directory',
448///   'name': <string>,
449///   'contents': [ <file or directory entries> ]
450/// }
451/// \endverbatim
452///
453/// The default attributes for virtual directories are:
454/// \verbatim
455/// MTime = now() when created
456/// Perms = 0777
457/// User = Group = 0
458/// Size = 0
459/// UniqueID = unspecified unique value
460/// \endverbatim
461///
462/// Re-mapped files are represented as
463/// \verbatim
464/// {
465///   'type': 'file',
466///   'name': <string>,
467///   'use-external-name': <boolean> # Optional
468///   'external-contents': <path to external file>)
469/// }
470/// \endverbatim
471///
472/// and inherit their attributes from the external contents.
473///
474/// In both cases, the 'name' field may contain multiple path components (e.g.
475/// /path/to/file). However, any directory that contains more than one child
476/// must be uniquely represented by a directory entry.
477class VFSFromYAML : public vfs::FileSystem {
478  std::vector<Entry *> Roots; ///< The root(s) of the virtual file system.
479  /// \brief The file system to use for external references.
480  IntrusiveRefCntPtr<FileSystem> ExternalFS;
481
482  /// @name Configuration
483  /// @{
484
485  /// \brief Whether to perform case-sensitive comparisons.
486  ///
487  /// Currently, case-insensitive matching only works correctly with ASCII.
488  bool CaseSensitive;
489
490  /// \brief Whether to use to use the value of 'external-contents' for the
491  /// names of files.  This global value is overridable on a per-file basis.
492  bool UseExternalNames;
493  /// @}
494
495  friend class VFSFromYAMLParser;
496
497private:
498  VFSFromYAML(IntrusiveRefCntPtr<FileSystem> ExternalFS)
499      : ExternalFS(ExternalFS), CaseSensitive(true), UseExternalNames(true) {}
500
501  /// \brief Looks up \p Path in \c Roots.
502  ErrorOr<Entry *> lookupPath(const Twine &Path);
503
504  /// \brief Looks up the path <tt>[Start, End)</tt> in \p From, possibly
505  /// recursing into the contents of \p From if it is a directory.
506  ErrorOr<Entry *> lookupPath(sys::path::const_iterator Start,
507                              sys::path::const_iterator End, Entry *From);
508
509  /// \brief Get the status of a given an \c Entry.
510  ErrorOr<Status> status(const Twine &Path, Entry *E);
511
512public:
513  ~VFSFromYAML();
514
515  /// \brief Parses \p Buffer, which is expected to be in YAML format and
516  /// returns a virtual file system representing its contents.
517  ///
518  /// Takes ownership of \p Buffer.
519  static VFSFromYAML *create(MemoryBuffer *Buffer,
520                             SourceMgr::DiagHandlerTy DiagHandler,
521                             void *DiagContext,
522                             IntrusiveRefCntPtr<FileSystem> ExternalFS);
523
524  ErrorOr<Status> status(const Twine &Path) override;
525  std::error_code openFileForRead(const Twine &Path,
526                                  std::unique_ptr<File> &Result) override;
527
528  directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override{
529    ErrorOr<Entry *> E = lookupPath(Dir);
530    if (!E) {
531      EC = E.getError();
532      return directory_iterator();
533    }
534    ErrorOr<Status> S = status(Dir, *E);
535    if (!S) {
536      EC = S.getError();
537      return directory_iterator();
538    }
539    if (!S->isDirectory()) {
540      EC = std::error_code(static_cast<int>(errc::not_a_directory),
541                           std::system_category());
542      return directory_iterator();
543    }
544
545    DirectoryEntry *D = cast<DirectoryEntry>(*E);
546    return directory_iterator(std::make_shared<VFSFromYamlDirIterImpl>(Dir,
547        *this, D->contents_begin(), D->contents_end(), EC));
548  }
549};
550
551/// \brief A helper class to hold the common YAML parsing state.
552class VFSFromYAMLParser {
553  yaml::Stream &Stream;
554
555  void error(yaml::Node *N, const Twine &Msg) {
556    Stream.printError(N, Msg);
557  }
558
559  // false on error
560  bool parseScalarString(yaml::Node *N, StringRef &Result,
561                         SmallVectorImpl<char> &Storage) {
562    yaml::ScalarNode *S = dyn_cast<yaml::ScalarNode>(N);
563    if (!S) {
564      error(N, "expected string");
565      return false;
566    }
567    Result = S->getValue(Storage);
568    return true;
569  }
570
571  // false on error
572  bool parseScalarBool(yaml::Node *N, bool &Result) {
573    SmallString<5> Storage;
574    StringRef Value;
575    if (!parseScalarString(N, Value, Storage))
576      return false;
577
578    if (Value.equals_lower("true") || Value.equals_lower("on") ||
579        Value.equals_lower("yes") || Value == "1") {
580      Result = true;
581      return true;
582    } else if (Value.equals_lower("false") || Value.equals_lower("off") ||
583               Value.equals_lower("no") || Value == "0") {
584      Result = false;
585      return true;
586    }
587
588    error(N, "expected boolean value");
589    return false;
590  }
591
592  struct KeyStatus {
593    KeyStatus(bool Required=false) : Required(Required), Seen(false) {}
594    bool Required;
595    bool Seen;
596  };
597  typedef std::pair<StringRef, KeyStatus> KeyStatusPair;
598
599  // false on error
600  bool checkDuplicateOrUnknownKey(yaml::Node *KeyNode, StringRef Key,
601                                  DenseMap<StringRef, KeyStatus> &Keys) {
602    if (!Keys.count(Key)) {
603      error(KeyNode, "unknown key");
604      return false;
605    }
606    KeyStatus &S = Keys[Key];
607    if (S.Seen) {
608      error(KeyNode, Twine("duplicate key '") + Key + "'");
609      return false;
610    }
611    S.Seen = true;
612    return true;
613  }
614
615  // false on error
616  bool checkMissingKeys(yaml::Node *Obj, DenseMap<StringRef, KeyStatus> &Keys) {
617    for (DenseMap<StringRef, KeyStatus>::iterator I = Keys.begin(),
618         E = Keys.end();
619         I != E; ++I) {
620      if (I->second.Required && !I->second.Seen) {
621        error(Obj, Twine("missing key '") + I->first + "'");
622        return false;
623      }
624    }
625    return true;
626  }
627
628  Entry *parseEntry(yaml::Node *N) {
629    yaml::MappingNode *M = dyn_cast<yaml::MappingNode>(N);
630    if (!M) {
631      error(N, "expected mapping node for file or directory entry");
632      return nullptr;
633    }
634
635    KeyStatusPair Fields[] = {
636      KeyStatusPair("name", true),
637      KeyStatusPair("type", true),
638      KeyStatusPair("contents", false),
639      KeyStatusPair("external-contents", false),
640      KeyStatusPair("use-external-name", false),
641    };
642
643    DenseMap<StringRef, KeyStatus> Keys(
644        &Fields[0], Fields + sizeof(Fields)/sizeof(Fields[0]));
645
646    bool HasContents = false; // external or otherwise
647    std::vector<Entry *> EntryArrayContents;
648    std::string ExternalContentsPath;
649    std::string Name;
650    FileEntry::NameKind UseExternalName = FileEntry::NK_NotSet;
651    EntryKind Kind;
652
653    for (yaml::MappingNode::iterator I = M->begin(), E = M->end(); I != E;
654         ++I) {
655      StringRef Key;
656      // Reuse the buffer for key and value, since we don't look at key after
657      // parsing value.
658      SmallString<256> Buffer;
659      if (!parseScalarString(I->getKey(), Key, Buffer))
660        return nullptr;
661
662      if (!checkDuplicateOrUnknownKey(I->getKey(), Key, Keys))
663        return nullptr;
664
665      StringRef Value;
666      if (Key == "name") {
667        if (!parseScalarString(I->getValue(), Value, Buffer))
668          return nullptr;
669        Name = Value;
670      } else if (Key == "type") {
671        if (!parseScalarString(I->getValue(), Value, Buffer))
672          return nullptr;
673        if (Value == "file")
674          Kind = EK_File;
675        else if (Value == "directory")
676          Kind = EK_Directory;
677        else {
678          error(I->getValue(), "unknown value for 'type'");
679          return nullptr;
680        }
681      } else if (Key == "contents") {
682        if (HasContents) {
683          error(I->getKey(),
684                "entry already has 'contents' or 'external-contents'");
685          return nullptr;
686        }
687        HasContents = true;
688        yaml::SequenceNode *Contents =
689            dyn_cast<yaml::SequenceNode>(I->getValue());
690        if (!Contents) {
691          // FIXME: this is only for directories, what about files?
692          error(I->getValue(), "expected array");
693          return nullptr;
694        }
695
696        for (yaml::SequenceNode::iterator I = Contents->begin(),
697                                          E = Contents->end();
698             I != E; ++I) {
699          if (Entry *E = parseEntry(&*I))
700            EntryArrayContents.push_back(E);
701          else
702            return nullptr;
703        }
704      } else if (Key == "external-contents") {
705        if (HasContents) {
706          error(I->getKey(),
707                "entry already has 'contents' or 'external-contents'");
708          return nullptr;
709        }
710        HasContents = true;
711        if (!parseScalarString(I->getValue(), Value, Buffer))
712          return nullptr;
713        ExternalContentsPath = Value;
714      } else if (Key == "use-external-name") {
715        bool Val;
716        if (!parseScalarBool(I->getValue(), Val))
717          return nullptr;
718        UseExternalName = Val ? FileEntry::NK_External : FileEntry::NK_Virtual;
719      } else {
720        llvm_unreachable("key missing from Keys");
721      }
722    }
723
724    if (Stream.failed())
725      return nullptr;
726
727    // check for missing keys
728    if (!HasContents) {
729      error(N, "missing key 'contents' or 'external-contents'");
730      return nullptr;
731    }
732    if (!checkMissingKeys(N, Keys))
733      return nullptr;
734
735    // check invalid configuration
736    if (Kind == EK_Directory && UseExternalName != FileEntry::NK_NotSet) {
737      error(N, "'use-external-name' is not supported for directories");
738      return nullptr;
739    }
740
741    // Remove trailing slash(es), being careful not to remove the root path
742    StringRef Trimmed(Name);
743    size_t RootPathLen = sys::path::root_path(Trimmed).size();
744    while (Trimmed.size() > RootPathLen &&
745           sys::path::is_separator(Trimmed.back()))
746      Trimmed = Trimmed.slice(0, Trimmed.size()-1);
747    // Get the last component
748    StringRef LastComponent = sys::path::filename(Trimmed);
749
750    Entry *Result = nullptr;
751    switch (Kind) {
752    case EK_File:
753      Result = new FileEntry(LastComponent, std::move(ExternalContentsPath),
754                             UseExternalName);
755      break;
756    case EK_Directory:
757      Result = new DirectoryEntry(LastComponent, std::move(EntryArrayContents),
758          Status("", "", getNextVirtualUniqueID(), sys::TimeValue::now(), 0, 0,
759                 0, file_type::directory_file, sys::fs::all_all));
760      break;
761    }
762
763    StringRef Parent = sys::path::parent_path(Trimmed);
764    if (Parent.empty())
765      return Result;
766
767    // if 'name' contains multiple components, create implicit directory entries
768    for (sys::path::reverse_iterator I = sys::path::rbegin(Parent),
769                                     E = sys::path::rend(Parent);
770         I != E; ++I) {
771      Result = new DirectoryEntry(*I, llvm::makeArrayRef(Result),
772          Status("", "", getNextVirtualUniqueID(), sys::TimeValue::now(), 0, 0,
773                 0, file_type::directory_file, sys::fs::all_all));
774    }
775    return Result;
776  }
777
778public:
779  VFSFromYAMLParser(yaml::Stream &S) : Stream(S) {}
780
781  // false on error
782  bool parse(yaml::Node *Root, VFSFromYAML *FS) {
783    yaml::MappingNode *Top = dyn_cast<yaml::MappingNode>(Root);
784    if (!Top) {
785      error(Root, "expected mapping node");
786      return false;
787    }
788
789    KeyStatusPair Fields[] = {
790      KeyStatusPair("version", true),
791      KeyStatusPair("case-sensitive", false),
792      KeyStatusPair("use-external-names", false),
793      KeyStatusPair("roots", true),
794    };
795
796    DenseMap<StringRef, KeyStatus> Keys(
797        &Fields[0], Fields + sizeof(Fields)/sizeof(Fields[0]));
798
799    // Parse configuration and 'roots'
800    for (yaml::MappingNode::iterator I = Top->begin(), E = Top->end(); I != E;
801         ++I) {
802      SmallString<10> KeyBuffer;
803      StringRef Key;
804      if (!parseScalarString(I->getKey(), Key, KeyBuffer))
805        return false;
806
807      if (!checkDuplicateOrUnknownKey(I->getKey(), Key, Keys))
808        return false;
809
810      if (Key == "roots") {
811        yaml::SequenceNode *Roots = dyn_cast<yaml::SequenceNode>(I->getValue());
812        if (!Roots) {
813          error(I->getValue(), "expected array");
814          return false;
815        }
816
817        for (yaml::SequenceNode::iterator I = Roots->begin(), E = Roots->end();
818             I != E; ++I) {
819          if (Entry *E = parseEntry(&*I))
820            FS->Roots.push_back(E);
821          else
822            return false;
823        }
824      } else if (Key == "version") {
825        StringRef VersionString;
826        SmallString<4> Storage;
827        if (!parseScalarString(I->getValue(), VersionString, Storage))
828          return false;
829        int Version;
830        if (VersionString.getAsInteger<int>(10, Version)) {
831          error(I->getValue(), "expected integer");
832          return false;
833        }
834        if (Version < 0) {
835          error(I->getValue(), "invalid version number");
836          return false;
837        }
838        if (Version != 0) {
839          error(I->getValue(), "version mismatch, expected 0");
840          return false;
841        }
842      } else if (Key == "case-sensitive") {
843        if (!parseScalarBool(I->getValue(), FS->CaseSensitive))
844          return false;
845      } else if (Key == "use-external-names") {
846        if (!parseScalarBool(I->getValue(), FS->UseExternalNames))
847          return false;
848      } else {
849        llvm_unreachable("key missing from Keys");
850      }
851    }
852
853    if (Stream.failed())
854      return false;
855
856    if (!checkMissingKeys(Top, Keys))
857      return false;
858    return true;
859  }
860};
861} // end of anonymous namespace
862
863Entry::~Entry() {}
864DirectoryEntry::~DirectoryEntry() { llvm::DeleteContainerPointers(Contents); }
865
866VFSFromYAML::~VFSFromYAML() { llvm::DeleteContainerPointers(Roots); }
867
868VFSFromYAML *VFSFromYAML::create(MemoryBuffer *Buffer,
869                                 SourceMgr::DiagHandlerTy DiagHandler,
870                                 void *DiagContext,
871                                 IntrusiveRefCntPtr<FileSystem> ExternalFS) {
872
873  SourceMgr SM;
874  yaml::Stream Stream(Buffer, SM);
875
876  SM.setDiagHandler(DiagHandler, DiagContext);
877  yaml::document_iterator DI = Stream.begin();
878  yaml::Node *Root = DI->getRoot();
879  if (DI == Stream.end() || !Root) {
880    SM.PrintMessage(SMLoc(), SourceMgr::DK_Error, "expected root node");
881    return nullptr;
882  }
883
884  VFSFromYAMLParser P(Stream);
885
886  std::unique_ptr<VFSFromYAML> FS(new VFSFromYAML(ExternalFS));
887  if (!P.parse(Root, FS.get()))
888    return nullptr;
889
890  return FS.release();
891}
892
893ErrorOr<Entry *> VFSFromYAML::lookupPath(const Twine &Path_) {
894  SmallString<256> Path;
895  Path_.toVector(Path);
896
897  // Handle relative paths
898  if (std::error_code EC = sys::fs::make_absolute(Path))
899    return EC;
900
901  if (Path.empty())
902    return make_error_code(llvm::errc::invalid_argument);
903
904  sys::path::const_iterator Start = sys::path::begin(Path);
905  sys::path::const_iterator End = sys::path::end(Path);
906  for (std::vector<Entry *>::iterator I = Roots.begin(), E = Roots.end();
907       I != E; ++I) {
908    ErrorOr<Entry *> Result = lookupPath(Start, End, *I);
909    if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
910      return Result;
911  }
912  return make_error_code(llvm::errc::no_such_file_or_directory);
913}
914
915ErrorOr<Entry *> VFSFromYAML::lookupPath(sys::path::const_iterator Start,
916                                         sys::path::const_iterator End,
917                                         Entry *From) {
918  if (Start->equals("."))
919    ++Start;
920
921  // FIXME: handle ..
922  if (CaseSensitive ? !Start->equals(From->getName())
923                    : !Start->equals_lower(From->getName()))
924    // failure to match
925    return make_error_code(llvm::errc::no_such_file_or_directory);
926
927  ++Start;
928
929  if (Start == End) {
930    // Match!
931    return From;
932  }
933
934  DirectoryEntry *DE = dyn_cast<DirectoryEntry>(From);
935  if (!DE)
936    return make_error_code(llvm::errc::not_a_directory);
937
938  for (DirectoryEntry::iterator I = DE->contents_begin(),
939                                E = DE->contents_end();
940       I != E; ++I) {
941    ErrorOr<Entry *> Result = lookupPath(Start, End, *I);
942    if (Result || Result.getError() != llvm::errc::no_such_file_or_directory)
943      return Result;
944  }
945  return make_error_code(llvm::errc::no_such_file_or_directory);
946}
947
948ErrorOr<Status> VFSFromYAML::status(const Twine &Path, Entry *E) {
949  assert(E != nullptr);
950  std::string PathStr(Path.str());
951  if (FileEntry *F = dyn_cast<FileEntry>(E)) {
952    ErrorOr<Status> S = ExternalFS->status(F->getExternalContentsPath());
953    assert(!S || S->getName() == F->getExternalContentsPath());
954    if (S && !F->useExternalName(UseExternalNames))
955      S->setName(PathStr);
956    if (S)
957      S->IsVFSMapped = true;
958    return S;
959  } else { // directory
960    DirectoryEntry *DE = cast<DirectoryEntry>(E);
961    Status S = DE->getStatus();
962    S.setName(PathStr);
963    return S;
964  }
965}
966
967ErrorOr<Status> VFSFromYAML::status(const Twine &Path) {
968  ErrorOr<Entry *> Result = lookupPath(Path);
969  if (!Result)
970    return Result.getError();
971  return status(Path, *Result);
972}
973
974std::error_code
975VFSFromYAML::openFileForRead(const Twine &Path,
976                             std::unique_ptr<vfs::File> &Result) {
977  ErrorOr<Entry *> E = lookupPath(Path);
978  if (!E)
979    return E.getError();
980
981  FileEntry *F = dyn_cast<FileEntry>(*E);
982  if (!F) // FIXME: errc::not_a_file?
983    return make_error_code(llvm::errc::invalid_argument);
984
985  if (std::error_code EC =
986          ExternalFS->openFileForRead(F->getExternalContentsPath(), Result))
987    return EC;
988
989  if (!F->useExternalName(UseExternalNames))
990    Result->setName(Path.str());
991
992  return std::error_code();
993}
994
995IntrusiveRefCntPtr<FileSystem>
996vfs::getVFSFromYAML(MemoryBuffer *Buffer, SourceMgr::DiagHandlerTy DiagHandler,
997                    void *DiagContext,
998                    IntrusiveRefCntPtr<FileSystem> ExternalFS) {
999  return VFSFromYAML::create(Buffer, DiagHandler, DiagContext, ExternalFS);
1000}
1001
1002UniqueID vfs::getNextVirtualUniqueID() {
1003  static std::atomic<unsigned> UID;
1004  unsigned ID = ++UID;
1005  // The following assumes that uint64_t max will never collide with a real
1006  // dev_t value from the OS.
1007  return UniqueID(std::numeric_limits<uint64_t>::max(), ID);
1008}
1009
1010#ifndef NDEBUG
1011static bool pathHasTraversal(StringRef Path) {
1012  using namespace llvm::sys;
1013  for (StringRef Comp : llvm::make_range(path::begin(Path), path::end(Path)))
1014    if (Comp == "." || Comp == "..")
1015      return true;
1016  return false;
1017}
1018#endif
1019
1020void YAMLVFSWriter::addFileMapping(StringRef VirtualPath, StringRef RealPath) {
1021  assert(sys::path::is_absolute(VirtualPath) && "virtual path not absolute");
1022  assert(sys::path::is_absolute(RealPath) && "real path not absolute");
1023  assert(!pathHasTraversal(VirtualPath) && "path traversal is not supported");
1024  Mappings.emplace_back(VirtualPath, RealPath);
1025}
1026
1027namespace {
1028class JSONWriter {
1029  llvm::raw_ostream &OS;
1030  SmallVector<StringRef, 16> DirStack;
1031  inline unsigned getDirIndent() { return 4 * DirStack.size(); }
1032  inline unsigned getFileIndent() { return 4 * (DirStack.size() + 1); }
1033  bool containedIn(StringRef Parent, StringRef Path);
1034  StringRef containedPart(StringRef Parent, StringRef Path);
1035  void startDirectory(StringRef Path);
1036  void endDirectory();
1037  void writeEntry(StringRef VPath, StringRef RPath);
1038
1039public:
1040  JSONWriter(llvm::raw_ostream &OS) : OS(OS) {}
1041  void write(ArrayRef<YAMLVFSEntry> Entries, Optional<bool> IsCaseSensitive);
1042};
1043}
1044
1045bool JSONWriter::containedIn(StringRef Parent, StringRef Path) {
1046  using namespace llvm::sys;
1047  // Compare each path component.
1048  auto IParent = path::begin(Parent), EParent = path::end(Parent);
1049  for (auto IChild = path::begin(Path), EChild = path::end(Path);
1050       IParent != EParent && IChild != EChild; ++IParent, ++IChild) {
1051    if (*IParent != *IChild)
1052      return false;
1053  }
1054  // Have we exhausted the parent path?
1055  return IParent == EParent;
1056}
1057
1058StringRef JSONWriter::containedPart(StringRef Parent, StringRef Path) {
1059  assert(!Parent.empty());
1060  assert(containedIn(Parent, Path));
1061  return Path.slice(Parent.size() + 1, StringRef::npos);
1062}
1063
1064void JSONWriter::startDirectory(StringRef Path) {
1065  StringRef Name =
1066      DirStack.empty() ? Path : containedPart(DirStack.back(), Path);
1067  DirStack.push_back(Path);
1068  unsigned Indent = getDirIndent();
1069  OS.indent(Indent) << "{\n";
1070  OS.indent(Indent + 2) << "'type': 'directory',\n";
1071  OS.indent(Indent + 2) << "'name': \"" << llvm::yaml::escape(Name) << "\",\n";
1072  OS.indent(Indent + 2) << "'contents': [\n";
1073}
1074
1075void JSONWriter::endDirectory() {
1076  unsigned Indent = getDirIndent();
1077  OS.indent(Indent + 2) << "]\n";
1078  OS.indent(Indent) << "}";
1079
1080  DirStack.pop_back();
1081}
1082
1083void JSONWriter::writeEntry(StringRef VPath, StringRef RPath) {
1084  unsigned Indent = getFileIndent();
1085  OS.indent(Indent) << "{\n";
1086  OS.indent(Indent + 2) << "'type': 'file',\n";
1087  OS.indent(Indent + 2) << "'name': \"" << llvm::yaml::escape(VPath) << "\",\n";
1088  OS.indent(Indent + 2) << "'external-contents': \""
1089                        << llvm::yaml::escape(RPath) << "\"\n";
1090  OS.indent(Indent) << "}";
1091}
1092
1093void JSONWriter::write(ArrayRef<YAMLVFSEntry> Entries,
1094                       Optional<bool> IsCaseSensitive) {
1095  using namespace llvm::sys;
1096
1097  OS << "{\n"
1098        "  'version': 0,\n";
1099  if (IsCaseSensitive.hasValue())
1100    OS << "  'case-sensitive': '"
1101       << (IsCaseSensitive.getValue() ? "true" : "false") << "',\n";
1102  OS << "  'roots': [\n";
1103
1104  if (Entries.empty())
1105    return;
1106
1107  const YAMLVFSEntry &Entry = Entries.front();
1108  startDirectory(path::parent_path(Entry.VPath));
1109  writeEntry(path::filename(Entry.VPath), Entry.RPath);
1110
1111  for (const auto &Entry : Entries.slice(1)) {
1112    StringRef Dir = path::parent_path(Entry.VPath);
1113    if (Dir == DirStack.back())
1114      OS << ",\n";
1115    else {
1116      while (!DirStack.empty() && !containedIn(DirStack.back(), Dir)) {
1117        OS << "\n";
1118        endDirectory();
1119      }
1120      OS << ",\n";
1121      startDirectory(Dir);
1122    }
1123    writeEntry(path::filename(Entry.VPath), Entry.RPath);
1124  }
1125
1126  while (!DirStack.empty()) {
1127    OS << "\n";
1128    endDirectory();
1129  }
1130
1131  OS << "\n"
1132     << "  ]\n"
1133     << "}\n";
1134}
1135
1136void YAMLVFSWriter::write(llvm::raw_ostream &OS) {
1137  std::sort(Mappings.begin(), Mappings.end(),
1138            [](const YAMLVFSEntry &LHS, const YAMLVFSEntry &RHS) {
1139    return LHS.VPath < RHS.VPath;
1140  });
1141
1142  JSONWriter(OS).write(Mappings, IsCaseSensitive);
1143}
1144
1145VFSFromYamlDirIterImpl::VFSFromYamlDirIterImpl(const Twine &_Path,
1146                                               VFSFromYAML &FS,
1147                                               DirectoryEntry::iterator Begin,
1148                                               DirectoryEntry::iterator End,
1149                                               std::error_code &EC)
1150    : Dir(_Path.str()), FS(FS), Current(Begin), End(End) {
1151  if (Current != End) {
1152    SmallString<128> PathStr(Dir);
1153    llvm::sys::path::append(PathStr, (*Current)->getName());
1154    llvm::ErrorOr<vfs::Status> S = FS.status(PathStr.str());
1155    if (S)
1156      CurrentEntry = *S;
1157    else
1158      EC = S.getError();
1159  }
1160}
1161
1162std::error_code VFSFromYamlDirIterImpl::increment() {
1163  assert(Current != End && "cannot iterate past end");
1164  if (++Current != End) {
1165    SmallString<128> PathStr(Dir);
1166    llvm::sys::path::append(PathStr, (*Current)->getName());
1167    llvm::ErrorOr<vfs::Status> S = FS.status(PathStr.str());
1168    if (!S)
1169      return S.getError();
1170    CurrentEntry = *S;
1171  } else {
1172    CurrentEntry = Status();
1173  }
1174  return std::error_code();
1175}
1176
1177vfs::recursive_directory_iterator::recursive_directory_iterator(FileSystem &FS_,
1178                                                           const Twine &Path,
1179                                                           std::error_code &EC)
1180    : FS(&FS_) {
1181  directory_iterator I = FS->dir_begin(Path, EC);
1182  if (!EC && I != directory_iterator()) {
1183    State = std::make_shared<IterState>();
1184    State->push(I);
1185  }
1186}
1187
1188vfs::recursive_directory_iterator &
1189recursive_directory_iterator::increment(std::error_code &EC) {
1190  assert(FS && State && !State->empty() && "incrementing past end");
1191  assert(State->top()->isStatusKnown() && "non-canonical end iterator");
1192  vfs::directory_iterator End;
1193  if (State->top()->isDirectory()) {
1194    vfs::directory_iterator I = FS->dir_begin(State->top()->getName(), EC);
1195    if (EC)
1196      return *this;
1197    if (I != End) {
1198      State->push(I);
1199      return *this;
1200    }
1201  }
1202
1203  while (!State->empty() && State->top().increment(EC) == End)
1204    State->pop();
1205
1206  if (State->empty())
1207    State.reset(); // end iterator
1208
1209  return *this;
1210}
1211