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