From 7c9f6c86c9fcbc60f8701e3bae13d7a0cc294939 Mon Sep 17 00:00:00 2001 From: Ben Langmuir Date: Wed, 25 Jun 2014 20:25:40 +0000 Subject: [PATCH] Add vfs::recursive_directory_iterator For now, this is only used by its unit tests. It is similar to the API in llvm::sys::fs::recursive_directory_iterator, but without some of the more complex features like requesting that the iterator not recurse into the next directory, for example. llvm-svn: 211732 --- clang/include/clang/Basic/VirtualFileSystem.h | 33 +++++++- clang/lib/Basic/VirtualFileSystem.cpp | 35 ++++++++ clang/unittests/Basic/VirtualFileSystemTest.cpp | 108 ++++++++++++++++++++++-- 3 files changed, 168 insertions(+), 8 deletions(-) diff --git a/clang/include/clang/Basic/VirtualFileSystem.h b/clang/include/clang/Basic/VirtualFileSystem.h index 3b43d1e..882ebdb 100644 --- a/clang/include/clang/Basic/VirtualFileSystem.h +++ b/clang/include/clang/Basic/VirtualFileSystem.h @@ -149,6 +149,37 @@ public: } }; +class FileSystem; + +/// \brief An input iterator over the recursive contents of a virtual path, +/// similar to llvm::sys::fs::recursive_directory_iterator. +class recursive_directory_iterator { + typedef std::stack> + IterState; + + FileSystem *FS; + std::shared_ptr State; // Input iterator semantics on copy. + +public: + recursive_directory_iterator(FileSystem &FS, const Twine &Path, + std::error_code &EC); + /// \brief Construct an 'end' iterator. + recursive_directory_iterator() { } + + /// \brief Equivalent to operator++, with an error code. + recursive_directory_iterator &increment(std::error_code &EC); + + const Status &operator*() const { return *State->top(); } + const Status *operator->() const { return &*State->top(); } + + bool operator==(const recursive_directory_iterator &Other) const { + return State == Other.State; // identity + } + bool operator!=(const recursive_directory_iterator &RHS) const { + return !(*this == RHS); + } +}; + /// \brief The virtual file system interface. class FileSystem : public llvm::ThreadSafeRefCountedBase { public: @@ -172,8 +203,6 @@ public: /// \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 diff --git a/clang/lib/Basic/VirtualFileSystem.cpp b/clang/lib/Basic/VirtualFileSystem.cpp index 253680e..3d5e1ad 100644 --- a/clang/lib/Basic/VirtualFileSystem.cpp +++ b/clang/lib/Basic/VirtualFileSystem.cpp @@ -1168,3 +1168,38 @@ std::error_code VFSFromYamlDirIterImpl::increment() { } return std::error_code(); } + +vfs::recursive_directory_iterator::recursive_directory_iterator(FileSystem &FS_, + const Twine &Path, + std::error_code &EC) + : FS(&FS_) { + directory_iterator I = FS->dir_begin(Path, EC); + if (!EC && I != directory_iterator()) { + State = std::make_shared(); + State->push(I); + } +} + +vfs::recursive_directory_iterator & +recursive_directory_iterator::increment(std::error_code &EC) { + assert(FS && State && !State->empty() && "incrementing past end"); + assert(State->top()->isStatusKnown() && "non-canonical end iterator"); + vfs::directory_iterator End; + if (State->top()->isDirectory()) { + vfs::directory_iterator I = FS->dir_begin(State->top()->getName(), EC); + if (EC) + return *this; + if (I != End) { + State->push(I); + return *this; + } + } + + while (!State->empty() && State->top().increment(EC) == End) + State->pop(); + + if (State->empty()) + State.reset(); // end iterator + + return *this; +} \ No newline at end of file diff --git a/clang/unittests/Basic/VirtualFileSystemTest.cpp b/clang/unittests/Basic/VirtualFileSystemTest.cpp index c416aa6..9289b22 100644 --- a/clang/unittests/Basic/VirtualFileSystemTest.cpp +++ b/clang/unittests/Basic/VirtualFileSystemTest.cpp @@ -54,12 +54,20 @@ public: std::map &FilesAndDirs; std::map::iterator I; std::string Path; + bool isInPath(StringRef S) { + if (Path.size() < S.size() && S.find(Path) == 0) { + auto LastSep = S.find_last_of('/'); + if (LastSep == Path.size() || LastSep == Path.size()-1) + return true; + } + return false; + } 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()) { + if (isInPath(I->first)) { CurrentEntry = I->second; break; } @@ -68,7 +76,7 @@ public: 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()) { + if (isInPath(I->first)) { CurrentEntry = I->second; break; } @@ -306,6 +314,46 @@ TEST(VirtualFileSystemTest, BasicRealFSIteration) { EXPECT_EQ(vfs::directory_iterator(), I); } +TEST(VirtualFileSystemTest, BasicRealFSRecursiveIteration) { + ScopedDir TestDirectory("virtual-file-system-test", /*Unique*/true); + IntrusiveRefCntPtr FS = vfs::getRealFileSystem(); + + std::error_code EC; + auto I = vfs::recursive_directory_iterator(*FS, Twine(TestDirectory), EC); + ASSERT_FALSE(EC); + EXPECT_EQ(vfs::recursive_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 = vfs::recursive_directory_iterator(*FS, Twine(TestDirectory), EC); + ASSERT_FALSE(EC); + ASSERT_NE(vfs::recursive_directory_iterator(), I); + + + std::vector Contents; + for (auto E = vfs::recursive_directory_iterator(); !EC && I != E; + I.increment(EC)) { + Contents.push_back(I->getName()); + } + + // Check contents, which may be in any order + EXPECT_EQ(4U, Contents.size()); + int Counts[4] = { 0, 0, 0, 0 }; + for (const std::string &Name : Contents) { + ASSERT_FALSE(Name.empty()); + int Index = Name[Name.size()-1] - 'a'; + ASSERT_TRUE(Index >= 0 && Index < 4); + Counts[Index]++; + } + EXPECT_EQ(1, Counts[0]); // a + EXPECT_EQ(1, Counts[1]); // b + EXPECT_EQ(1, Counts[2]); // c + EXPECT_EQ(1, Counts[3]); // d +} + template std::vector makeStringRefVector(const T (&Arr)[N]) { std::vector Vec; @@ -314,17 +362,17 @@ std::vector makeStringRefVector(const T (&Arr)[N]) { return Vec; } -static void checkContents(vfs::directory_iterator I, - ArrayRef Expected) { +template +static void checkContents(DirIter I, ArrayRef Expected) { std::error_code EC; auto ExpectedIter = Expected.begin(), ExpectedEnd = Expected.end(); - for (vfs::directory_iterator E; + for (DirIter 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); + EXPECT_EQ(DirIter(), I); } TEST(VirtualFileSystemTest, OverlayIteration) { @@ -357,6 +405,54 @@ TEST(VirtualFileSystemTest, OverlayIteration) { } } +TEST(VirtualFileSystemTest, OverlayRecursiveIteration) { + 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(vfs::recursive_directory_iterator(*O, "/", EC), + ArrayRef()); + + Lower->addRegularFile("/file1"); + checkContents(vfs::recursive_directory_iterator(*O, "/", EC), + ArrayRef("/file1")); + + Upper->addDirectory("/dir"); + Upper->addRegularFile("/dir/file2"); + { + const char *Contents[] = {"/dir", "/dir/file2", "/file1"}; + checkContents(vfs::recursive_directory_iterator(*O, "/", EC), + makeStringRefVector(Contents)); + } + + Lower->addDirectory("/dir1"); + Lower->addRegularFile("/dir1/foo"); + Lower->addDirectory("/dir1/a"); + Lower->addRegularFile("/dir1/a/b"); + Middle->addDirectory("/a"); + Middle->addDirectory("/a/b"); + Middle->addDirectory("/a/b/c"); + Middle->addRegularFile("/a/b/c/d"); + Middle->addRegularFile("/hiddenByUp"); + Upper->addDirectory("/dir2"); + Upper->addRegularFile("/dir2/foo"); + Upper->addRegularFile("/hiddenByUp"); + checkContents(vfs::recursive_directory_iterator(*O, "/dir2", EC), + ArrayRef("/dir2/foo")); + { + const char *Contents[] = { "/dir", "/dir/file2", "/dir2", "/dir2/foo", + "/hiddenByUp", "/a", "/a/b", "/a/b/c", "/a/b/c/d", "/dir1", "/dir1/a", + "/dir1/a/b", "/dir1/foo", "/file1" }; + checkContents(vfs::recursive_directory_iterator(*O, "/", EC), + makeStringRefVector(Contents)); + } +} + TEST(VirtualFileSystemTest, ThreeLevelIteration) { IntrusiveRefCntPtr Lower(new DummyFileSystem()); IntrusiveRefCntPtr Middle(new DummyFileSystem()); -- 2.7.4