From 740812bb9a4a47dce964f60f8e623a0386335296 Mon Sep 17 00:00:00 2001 From: Ben Langmuir Date: Tue, 24 Jun 2014 19:37:16 +0000 Subject: [PATCH] Add directory_iterator for (non-recursive) iteration of VFS directories The API is based on sys::fs::directory_iterator, but it allows iterating over overlays and the yaml-based VFS. For now, it isn't used by anything (except its tests). llvm-svn: 211623 --- clang/include/clang/Basic/VirtualFileSystem.h | 84 +++++++- clang/lib/Basic/VirtualFileSystem.cpp | 198 ++++++++++++++++++- clang/unittests/Basic/VirtualFileSystemTest.cpp | 242 ++++++++++++++++++++++++ 3 files changed, 508 insertions(+), 16 deletions(-) diff --git a/clang/include/clang/Basic/VirtualFileSystem.h b/clang/include/clang/Basic/VirtualFileSystem.h index 83e0fb5..8c83012 100644 --- a/clang/include/clang/Basic/VirtualFileSystem.h +++ b/clang/include/clang/Basic/VirtualFileSystem.h @@ -100,6 +100,64 @@ public: virtual void setName(StringRef Name) = 0; }; +namespace detail { +/// \brief An interface for virtual file systems to provide an iterator over the +/// (non-recursive) contents of a directory. +struct DirIterImpl { + virtual ~DirIterImpl(); + /// \brief Sets \c CurrentEntry to the next entry in the directory on success, + /// or returns a system-defined \c error_code. + virtual std::error_code increment() = 0; + Status CurrentEntry; +}; +} // end namespace detail + +/// \brief An input iterator over the entries in a virtual path, similar to +/// llvm::sys::fs::directory_iterator. +class directory_iterator { + std::shared_ptr Impl; // Input iterator semantics on copy + +public: + directory_iterator(std::shared_ptr I) : Impl(I) { + assert(Impl.get() != nullptr && "requires non-null implementation"); + if (!Impl->CurrentEntry.isStatusKnown()) + Impl.reset(); // Normalize the end iterator to Impl == nullptr. + } + + /// \brief Construct an 'end' iterator. + directory_iterator() { } + + /// \brief Equivalent to operator++, with an error code. + directory_iterator &increment(std::error_code &EC) { + assert(Impl && "attempting to increment past end"); + EC = Impl->increment(); + if (EC || !Impl->CurrentEntry.isStatusKnown()) + Impl.reset(); // Normalize the end iterator to Impl == nullptr. + return *this; + } + + const Status &operator*() const { return Impl->CurrentEntry; } + const Status *operator->() const { return &Impl->CurrentEntry; } + + bool operator==(const directory_iterator &RHS) const { + if (Impl && RHS.Impl) + return Impl->CurrentEntry.equivalent(RHS.Impl->CurrentEntry); + return !Impl && !RHS.Impl; + } + bool operator!=(const directory_iterator &RHS) const { + return !(*this == RHS); + } + + /// For testing only. Directory iteration does not always succeed! + directory_iterator &operator++() { + std::error_code EC; + increment(EC); + if (EC) + llvm::report_fatal_error("directory iteration failed!"); + return *this; + } +}; + /// \brief The virtual file system interface. class FileSystem : public llvm::ThreadSafeRefCountedBase { public: @@ -118,6 +176,13 @@ public: int64_t FileSize = -1, bool RequiresNullTerminator = true, bool IsVolatile = false); + + /// \brief Get a directory_iterator for \p Dir. + /// \note The 'end' iterator is directory_iterator() + virtual directory_iterator dir_begin(const Twine &Dir, + std::error_code &EC) = 0; + + // TODO: recursive directory iterators }; /// \brief Gets an \p vfs::FileSystem for the 'real' file system, as seen by @@ -136,19 +201,10 @@ IntrusiveRefCntPtr getRealFileSystem(); /// system overrides the other(s). class OverlayFileSystem : public FileSystem { typedef SmallVector, 1> FileSystemList; - typedef FileSystemList::reverse_iterator iterator; - /// \brief The stack of file systems, implemented as a list in order of /// their addition. FileSystemList FSList; - /// \brief Get an iterator pointing to the most recently added file system. - iterator overlays_begin() { return FSList.rbegin(); } - - /// \brief Get an iterator pointing one-past the least recently added file - /// system. - iterator overlays_end() { return FSList.rend(); } - public: OverlayFileSystem(IntrusiveRefCntPtr Base); /// \brief Pushes a file system on top of the stack. @@ -157,6 +213,16 @@ public: llvm::ErrorOr status(const Twine &Path) override; std::error_code openFileForRead(const Twine &Path, std::unique_ptr &Result) override; + directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override; + + typedef FileSystemList::reverse_iterator iterator; + + /// \brief Get an iterator pointing to the most recently added file system. + iterator overlays_begin() { return FSList.rbegin(); } + + /// \brief Get an iterator pointing one-past the least recently added file + /// system. + iterator overlays_end() { return FSList.rend(); } }; /// \brief Get a globally unique ID for a virtual file or directory. diff --git a/clang/lib/Basic/VirtualFileSystem.cpp b/clang/lib/Basic/VirtualFileSystem.cpp index 63302b7..253680e 100644 --- a/clang/lib/Basic/VirtualFileSystem.cpp +++ b/clang/lib/Basic/VirtualFileSystem.cpp @@ -14,6 +14,7 @@ #include "llvm/ADT/iterator_range.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/ADT/StringSet.h" #include "llvm/Support/Errc.h" #include "llvm/Support/MemoryBuffer.h" #include "llvm/Support/Path.h" @@ -157,6 +158,7 @@ public: ErrorOr status(const Twine &Path) override; std::error_code openFileForRead(const Twine &Path, std::unique_ptr &Result) override; + directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override; }; } // end anonymous namespace @@ -184,6 +186,46 @@ IntrusiveRefCntPtr vfs::getRealFileSystem() { return FS; } +namespace { +class RealFSDirIter : public clang::vfs::detail::DirIterImpl { + std::string Path; + llvm::sys::fs::directory_iterator Iter; +public: + RealFSDirIter(const Twine &_Path, std::error_code &EC) + : Path(_Path.str()), Iter(Path, EC) { + if (!EC && Iter != llvm::sys::fs::directory_iterator()) { + llvm::sys::fs::file_status S; + EC = Iter->status(S); + if (!EC) { + CurrentEntry = Status(S); + CurrentEntry.setName(Iter->path()); + } + } + } + + std::error_code increment() override { + std::error_code EC; + Iter.increment(EC); + if (EC) { + return EC; + } else if (Iter == llvm::sys::fs::directory_iterator()) { + CurrentEntry = Status(); + } else { + llvm::sys::fs::file_status S; + EC = Iter->status(S); + CurrentEntry = Status(S); + CurrentEntry.setName(Iter->path()); + } + return EC; + } +}; +} + +directory_iterator RealFileSystem::dir_begin(const Twine &Dir, + std::error_code &EC) { + return directory_iterator(std::make_shared(Dir, EC)); +} + //===-----------------------------------------------------------------------===/ // OverlayFileSystem implementation //===-----------------------------------------------------------------------===/ @@ -217,6 +259,74 @@ OverlayFileSystem::openFileForRead(const llvm::Twine &Path, return make_error_code(llvm::errc::no_such_file_or_directory); } +clang::vfs::detail::DirIterImpl::~DirIterImpl() { } + +namespace { +class OverlayFSDirIterImpl : public clang::vfs::detail::DirIterImpl { + OverlayFileSystem &Overlays; + std::string Path; + OverlayFileSystem::iterator CurrentFS; + directory_iterator CurrentDirIter; + llvm::StringSet<> SeenNames; + + std::error_code incrementFS() { + assert(CurrentFS != Overlays.overlays_end() && "incrementing past end"); + ++CurrentFS; + for (auto E = Overlays.overlays_end(); CurrentFS != E; ++CurrentFS) { + std::error_code EC; + CurrentDirIter = (*CurrentFS)->dir_begin(Path, EC); + if (EC && EC != errc::no_such_file_or_directory) + return EC; + if (CurrentDirIter != directory_iterator()) + break; // found + } + return std::error_code(); + } + + std::error_code incrementDirIter(bool IsFirstTime) { + assert((IsFirstTime || CurrentDirIter != directory_iterator()) && + "incrementing past end"); + std::error_code EC; + if (!IsFirstTime) + CurrentDirIter.increment(EC); + if (!EC && CurrentDirIter == directory_iterator()) + EC = incrementFS(); + return EC; + } + + std::error_code incrementImpl(bool IsFirstTime) { + while (true) { + std::error_code EC = incrementDirIter(IsFirstTime); + if (EC || CurrentDirIter == directory_iterator()) { + CurrentEntry = Status(); + return EC; + } + CurrentEntry = *CurrentDirIter; + StringRef Name = llvm::sys::path::filename(CurrentEntry.getName()); + if (SeenNames.insert(Name)) + return EC; // name not seen before + } + llvm_unreachable("returned above"); + } + +public: + OverlayFSDirIterImpl(const Twine &Path, OverlayFileSystem &FS, + std::error_code &EC) + : Overlays(FS), Path(Path.str()), CurrentFS(Overlays.overlays_begin()) { + CurrentDirIter = (*CurrentFS)->dir_begin(Path, EC); + EC = incrementImpl(true); + } + + std::error_code increment() override { return incrementImpl(false); } +}; +} // end anonymous namespace + +directory_iterator OverlayFileSystem::dir_begin(const Twine &Dir, + std::error_code &EC) { + return directory_iterator( + std::make_shared(Dir, *this, EC)); +} + //===-----------------------------------------------------------------------===/ // VFSFromYAML implementation //===-----------------------------------------------------------------------===/ @@ -293,6 +403,19 @@ public: static bool classof(const Entry *E) { return E->getKind() == EK_File; } }; +class VFSFromYAML; + +class VFSFromYamlDirIterImpl : public clang::vfs::detail::DirIterImpl { + std::string Dir; + VFSFromYAML &FS; + DirectoryEntry::iterator Current, End; +public: + VFSFromYamlDirIterImpl(const Twine &Path, VFSFromYAML &FS, + DirectoryEntry::iterator Begin, + DirectoryEntry::iterator End, std::error_code &EC); + std::error_code increment() override; +}; + /// \brief A virtual file system parsed from a YAML file. /// /// Currently, this class allows creating virtual directories and mapping @@ -378,6 +501,9 @@ private: ErrorOr lookupPath(sys::path::const_iterator Start, sys::path::const_iterator End, Entry *From); + /// \brief Get the status of a given an \c Entry. + ErrorOr status(const Twine &Path, Entry *E); + public: ~VFSFromYAML(); @@ -393,6 +519,28 @@ public: ErrorOr status(const Twine &Path) override; std::error_code openFileForRead(const Twine &Path, std::unique_ptr &Result) override; + + directory_iterator dir_begin(const Twine &Dir, std::error_code &EC) override{ + ErrorOr E = lookupPath(Dir); + if (!E) { + EC = E.getError(); + return directory_iterator(); + } + ErrorOr S = status(Dir, *E); + if (!S) { + EC = S.getError(); + return directory_iterator(); + } + if (!S->isDirectory()) { + EC = std::error_code(static_cast(errc::not_a_directory), + std::system_category()); + return directory_iterator(); + } + + DirectoryEntry *D = cast(*E); + return directory_iterator(std::make_shared(Dir, + *this, D->contents_begin(), D->contents_end(), EC)); + } }; /// \brief A helper class to hold the common YAML parsing state. @@ -792,13 +940,10 @@ ErrorOr VFSFromYAML::lookupPath(sys::path::const_iterator Start, return make_error_code(llvm::errc::no_such_file_or_directory); } -ErrorOr VFSFromYAML::status(const Twine &Path) { - ErrorOr Result = lookupPath(Path); - if (!Result) - return Result.getError(); - +ErrorOr VFSFromYAML::status(const Twine &Path, Entry *E) { + assert(E != nullptr); std::string PathStr(Path.str()); - if (FileEntry *F = dyn_cast(*Result)) { + if (FileEntry *F = dyn_cast(E)) { ErrorOr S = ExternalFS->status(F->getExternalContentsPath()); assert(!S || S->getName() == F->getExternalContentsPath()); if (S && !F->useExternalName(UseExternalNames)) @@ -807,13 +952,20 @@ ErrorOr VFSFromYAML::status(const Twine &Path) { S->IsVFSMapped = true; return S; } else { // directory - DirectoryEntry *DE = cast(*Result); + DirectoryEntry *DE = cast(E); Status S = DE->getStatus(); S.setName(PathStr); return S; } } +ErrorOr VFSFromYAML::status(const Twine &Path) { + ErrorOr Result = lookupPath(Path); + if (!Result) + return Result.getError(); + return status(Path, *Result); +} + std::error_code VFSFromYAML::openFileForRead(const Twine &Path, std::unique_ptr &Result) { @@ -984,3 +1136,35 @@ void YAMLVFSWriter::write(llvm::raw_ostream &OS) { JSONWriter(OS).write(Mappings, IsCaseSensitive); } + +VFSFromYamlDirIterImpl::VFSFromYamlDirIterImpl(const Twine &_Path, + VFSFromYAML &FS, + DirectoryEntry::iterator Begin, + DirectoryEntry::iterator End, + std::error_code &EC) + : Dir(_Path.str()), FS(FS), Current(Begin), End(End) { + if (Current != End) { + SmallString<128> PathStr(Dir); + llvm::sys::path::append(PathStr, (*Current)->getName()); + llvm::ErrorOr S = FS.status(PathStr.str()); + if (S) + CurrentEntry = *S; + else + EC = S.getError(); + } +} + +std::error_code VFSFromYamlDirIterImpl::increment() { + assert(Current != End && "cannot iterate past end"); + if (++Current != End) { + SmallString<128> PathStr(Dir); + llvm::sys::path::append(PathStr, (*Current)->getName()); + llvm::ErrorOr S = FS.status(PathStr.str()); + if (!S) + return S.getError(); + CurrentEntry = *S; + } else { + CurrentEntry = Status(); + } + return std::error_code(); +} diff --git a/clang/unittests/Basic/VirtualFileSystemTest.cpp b/clang/unittests/Basic/VirtualFileSystemTest.cpp index 132e248f2..084819a6 100644 --- a/clang/unittests/Basic/VirtualFileSystemTest.cpp +++ b/clang/unittests/Basic/VirtualFileSystemTest.cpp @@ -50,6 +50,41 @@ public: llvm_unreachable("unimplemented"); } + struct DirIterImpl : public clang::vfs::detail::DirIterImpl { + std::map &FilesAndDirs; + std::map::iterator I; + std::string Path; + DirIterImpl(std::map &FilesAndDirs, + const Twine &_Path) + : FilesAndDirs(FilesAndDirs), I(FilesAndDirs.begin()), + Path(_Path.str()) { + for ( ; I != FilesAndDirs.end(); ++I) { + if (Path.size() < I->first.size() && I->first.find(Path) == 0 && I->first.find_last_of('/') <= Path.size()) { + CurrentEntry = I->second; + break; + } + } + } + std::error_code increment() override { + ++I; + for ( ; I != FilesAndDirs.end(); ++I) { + if (Path.size() < I->first.size() && I->first.find(Path) == 0 && I->first.find_last_of('/') <= Path.size()) { + CurrentEntry = I->second; + break; + } + } + if (I == FilesAndDirs.end()) + CurrentEntry = vfs::Status(); + return std::error_code(); + } + }; + + vfs::directory_iterator dir_begin(const Twine &Dir, + std::error_code &EC) override { + return vfs::directory_iterator( + std::make_shared(FilesAndDirs, Dir)); + } + void addEntry(StringRef Path, const vfs::Status &Status) { FilesAndDirs[Path] = Status; } @@ -221,6 +256,163 @@ TEST(VirtualFileSystemTest, MergedDirPermissions) { EXPECT_EQ(0200, Status->getPermissions()); } +namespace { +struct ScopedDir { + SmallString<128> Path; + ScopedDir(const Twine &Name, bool Unique=false) { + std::error_code EC; + if (Unique) { + EC = llvm::sys::fs::createUniqueDirectory(Name, Path); + } else { + Path = Name.str(); + EC = llvm::sys::fs::create_directory(Twine(Path)); + } + if (EC) + Path = ""; + EXPECT_FALSE(EC); + } + ~ScopedDir() { + if (Path != "") + EXPECT_FALSE(llvm::sys::fs::remove(Path.str())); + } + operator StringRef() { return Path.str(); } +}; +} + +TEST(VirtualFileSystemTest, BasicRealFSIteration) { + ScopedDir TestDirectory("virtual-file-system-test", /*Unique*/true); + IntrusiveRefCntPtr FS = vfs::getRealFileSystem(); + + std::error_code EC; + vfs::directory_iterator I = FS->dir_begin(Twine(TestDirectory), EC); + ASSERT_FALSE(EC); + EXPECT_EQ(vfs::directory_iterator(), I); // empty directory is empty + + ScopedDir _a(TestDirectory+"/a"); + ScopedDir _ab(TestDirectory+"/a/b"); + ScopedDir _c(TestDirectory+"/c"); + ScopedDir _cd(TestDirectory+"/c/d"); + + I = FS->dir_begin(Twine(TestDirectory), EC); + ASSERT_FALSE(EC); + ASSERT_NE(vfs::directory_iterator(), I); + EXPECT_TRUE(I->getName().endswith("a")); + I.increment(EC); + ASSERT_FALSE(EC); + ASSERT_NE(vfs::directory_iterator(), I); + EXPECT_TRUE(I->getName().endswith("c")); + I.increment(EC); + EXPECT_EQ(vfs::directory_iterator(), I); +} + +static void checkContents(vfs::directory_iterator I, + ArrayRef Expected) { + std::error_code EC; + auto ExpectedIter = Expected.begin(), ExpectedEnd = Expected.end(); + for (vfs::directory_iterator E; + !EC && I != E && ExpectedIter != ExpectedEnd; + I.increment(EC), ++ExpectedIter) + EXPECT_EQ(*ExpectedIter, I->getName()); + + EXPECT_EQ(ExpectedEnd, ExpectedIter); + EXPECT_EQ(vfs::directory_iterator(), I); +} + +TEST(VirtualFileSystemTest, OverlayIteration) { + IntrusiveRefCntPtr Lower(new DummyFileSystem()); + IntrusiveRefCntPtr Upper(new DummyFileSystem()); + IntrusiveRefCntPtr O( + new vfs::OverlayFileSystem(Lower)); + O->pushOverlay(Upper); + + std::error_code EC; + checkContents(O->dir_begin("/", EC), ArrayRef()); + + Lower->addRegularFile("/file1"); + checkContents(O->dir_begin("/", EC), ArrayRef("/file1")); + + Upper->addRegularFile("/file2"); + { + std::vector Contents = { "/file2", "/file1" }; + checkContents(O->dir_begin("/", EC), Contents); + } + + Lower->addDirectory("/dir1"); + Lower->addRegularFile("/dir1/foo"); + Upper->addDirectory("/dir2"); + Upper->addRegularFile("/dir2/foo"); + checkContents(O->dir_begin("/dir2", EC), ArrayRef("/dir2/foo")); + { + std::vector Contents = { "/dir2", "/file2", "/dir1", "/file1" }; + checkContents(O->dir_begin("/", EC), Contents); + } +} + +TEST(VirtualFileSystemTest, ThreeLevelIteration) { + IntrusiveRefCntPtr Lower(new DummyFileSystem()); + IntrusiveRefCntPtr Middle(new DummyFileSystem()); + IntrusiveRefCntPtr Upper(new DummyFileSystem()); + IntrusiveRefCntPtr O( + new vfs::OverlayFileSystem(Lower)); + O->pushOverlay(Middle); + O->pushOverlay(Upper); + + std::error_code EC; + checkContents(O->dir_begin("/", EC), ArrayRef()); + + Middle->addRegularFile("/file2"); + checkContents(O->dir_begin("/", EC), ArrayRef("/file2")); + + Lower->addRegularFile("/file1"); + Upper->addRegularFile("/file3"); + { + std::vector Contents = { "/file3", "/file2", "/file1" }; + checkContents(O->dir_begin("/", EC), Contents); + } +} + +TEST(VirtualFileSystemTest, HiddenInIteration) { + IntrusiveRefCntPtr Lower(new DummyFileSystem()); + IntrusiveRefCntPtr Middle(new DummyFileSystem()); + IntrusiveRefCntPtr Upper(new DummyFileSystem()); + IntrusiveRefCntPtr O( + new vfs::OverlayFileSystem(Lower)); + O->pushOverlay(Middle); + O->pushOverlay(Upper); + + std::error_code EC; + Lower->addRegularFile("/onlyInLow", sys::fs::owner_read); + Lower->addRegularFile("/hiddenByMid", sys::fs::owner_read); + Lower->addRegularFile("/hiddenByUp", sys::fs::owner_read); + Middle->addRegularFile("/onlyInMid", sys::fs::owner_write); + Middle->addRegularFile("/hiddenByMid", sys::fs::owner_write); + Middle->addRegularFile("/hiddenByUp", sys::fs::owner_write); + Upper->addRegularFile("/onlyInUp", sys::fs::owner_all); + Upper->addRegularFile("/hiddenByUp", sys::fs::owner_all); + { + std::vector Contents = { "/hiddenByUp", "/onlyInUp", + "/hiddenByMid", "/onlyInMid", "/onlyInLow" }; + checkContents(O->dir_begin("/", EC), Contents); + } + + // Make sure we get the top-most entry + vfs::directory_iterator E; + { + auto I = std::find_if(O->dir_begin("/", EC), E, [](vfs::Status S){ + return S.getName() == "/hiddenByUp"; + }); + ASSERT_NE(E, I); + EXPECT_EQ(sys::fs::owner_all, I->getPermissions()); + } + { + auto I = std::find_if(O->dir_begin("/", EC), E, [](vfs::Status S){ + return S.getName() == "/hiddenByMid"; + }); + ASSERT_NE(E, I); + EXPECT_EQ(sys::fs::owner_write, I->getPermissions()); + } +} + // NOTE: in the tests below, we use '//root/' as our root directory, since it is // a legal *absolute* path on Windows as well as *nix. class VFSFromYAMLTest : public ::testing::Test { @@ -583,3 +775,53 @@ TEST_F(VFSFromYAMLTest, TrailingSlashes) { EXPECT_FALSE(FS->status("//root/path").getError()); EXPECT_FALSE(FS->status("//root/").getError()); } + +TEST_F(VFSFromYAMLTest, DirectoryIteration) { + IntrusiveRefCntPtr Lower(new DummyFileSystem()); + Lower->addDirectory("//root/"); + Lower->addDirectory("//root/foo"); + Lower->addDirectory("//root/foo/bar"); + Lower->addRegularFile("//root/foo/bar/a"); + Lower->addRegularFile("//root/foo/bar/b"); + Lower->addRegularFile("//root/file3"); + IntrusiveRefCntPtr FS = + getFromYAMLString("{ 'use-external-names': false,\n" + " 'roots': [\n" + "{\n" + " 'type': 'directory',\n" + " 'name': '//root/',\n" + " 'contents': [ {\n" + " 'type': 'file',\n" + " 'name': 'file1',\n" + " 'external-contents': '//root/foo/bar/a'\n" + " },\n" + " {\n" + " 'type': 'file',\n" + " 'name': 'file2',\n" + " 'external-contents': '//root/foo/bar/b'\n" + " }\n" + " ]\n" + "}\n" + "]\n" + "}", + Lower); + ASSERT_TRUE(FS.getPtr() != NULL); + + IntrusiveRefCntPtr O( + new vfs::OverlayFileSystem(Lower)); + O->pushOverlay(FS); + + std::error_code EC; + { + std::vector Contents = { "//root/file1", "//root/file2", + "//root/file3", "//root/foo" }; + checkContents(O->dir_begin("//root/", EC), Contents); + } + + { + std::vector Contents = { + "//root/foo/bar/a", "//root/foo/bar/b" }; + checkContents(O->dir_begin("//root/foo/bar", EC), Contents); + } +} + -- 2.7.4