From a81ac8f2b5d4f61f7bc353f95cc1d0a05266f51c Mon Sep 17 00:00:00 2001 From: "Michael J. Spencer" Date: Thu, 8 Dec 2011 22:50:09 +0000 Subject: [PATCH] Support/FileSystem: Implement recursive_directory_iterator and make directory_iterator preserve InputIterator semantics on copy. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146200 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/IntrusiveRefCntPtr.h | 7 +- include/llvm/Support/FileSystem.h | 162 +++++++++++++++++++++----- lib/Support/Unix/PathV2.inc | 7 +- lib/Support/Windows/PathV2.inc | 13 ++- unittests/Support/Path.cpp | 51 ++++++++ 5 files changed, 198 insertions(+), 42 deletions(-) diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h index 8757f00d73c..106daf41799 100644 --- a/include/llvm/ADT/IntrusiveRefCntPtr.h +++ b/include/llvm/ADT/IntrusiveRefCntPtr.h @@ -156,7 +156,12 @@ namespace llvm { other.Obj = Obj; Obj = tmp; } - + + void reset() { + release(); + Obj = 0; + } + void resetWithoutRelease() { Obj = 0; } diff --git a/include/llvm/Support/FileSystem.h b/include/llvm/Support/FileSystem.h index a868e5f9f70..42e61dcba72 100644 --- a/include/llvm/Support/FileSystem.h +++ b/include/llvm/Support/FileSystem.h @@ -27,13 +27,16 @@ #ifndef LLVM_SUPPORT_FILE_SYSTEM_H #define LLVM_SUPPORT_FILE_SYSTEM_H +#include "llvm/ADT/IntrusiveRefCntPtr.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/Twine.h" #include "llvm/Support/DataTypes.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/PathV1.h" #include "llvm/Support/system_error.h" #include #include +#include #include namespace llvm { @@ -479,76 +482,171 @@ public: bool operator>=(const directory_entry& rhs) const; }; +namespace detail { + struct DirIterState; + + error_code directory_iterator_construct(DirIterState&, StringRef); + error_code directory_iterator_increment(DirIterState&); + error_code directory_iterator_destruct(DirIterState&); + + /// DirIterState - Keeps state for the directory_iterator. It is reference + /// counted in order to preserve InputIterator semantics on copy. + struct DirIterState : public RefCountedBase { + DirIterState() + : IterationHandle(0) {} + + ~DirIterState() { + directory_iterator_destruct(*this); + } + + intptr_t IterationHandle; + directory_entry CurrentEntry; + }; +} + /// directory_iterator - Iterates through the entries in path. There is no /// operator++ because we need an error_code. If it's really needed we can make /// it call report_fatal_error on error. class directory_iterator { - intptr_t IterationHandle; - directory_entry CurrentEntry; - - // Platform implementations implement these functions to handle iteration. - friend error_code directory_iterator_construct(directory_iterator &it, - StringRef path); - friend error_code directory_iterator_increment(directory_iterator &it); - friend error_code directory_iterator_destruct(directory_iterator &it); + IntrusiveRefCntPtr State; public: - explicit directory_iterator(const Twine &path, error_code &ec) - : IterationHandle(0) { + explicit directory_iterator(const Twine &path, error_code &ec) { + State = new detail::DirIterState; SmallString<128> path_storage; - ec = directory_iterator_construct(*this, path.toStringRef(path_storage)); + ec = detail::directory_iterator_construct(*State, + path.toStringRef(path_storage)); } - /// Construct end iterator. - directory_iterator() : IterationHandle(0) {} - - ~directory_iterator() { - directory_iterator_destruct(*this); + explicit directory_iterator(const directory_entry &de, error_code &ec) { + State = new detail::DirIterState; + ec = detail::directory_iterator_construct(*State, de.path()); } + /// Construct end iterator. + directory_iterator() : State(new detail::DirIterState) {} + // No operator++ because we need error_code. directory_iterator &increment(error_code &ec) { - ec = directory_iterator_increment(*this); + ec = directory_iterator_increment(*State); return *this; } - const directory_entry &operator*() const { return CurrentEntry; } - const directory_entry *operator->() const { return &CurrentEntry; } + const directory_entry &operator*() const { return State->CurrentEntry; } + const directory_entry *operator->() const { return &State->CurrentEntry; } + + bool operator==(const directory_iterator &RHS) const { + return State->CurrentEntry == RHS.State->CurrentEntry; + } bool operator!=(const directory_iterator &RHS) const { - return CurrentEntry != RHS.CurrentEntry; + return !(*this == RHS); } // Other members as required by // C++ Std, 24.1.1 Input iterators [input.iterators] }; +namespace detail { + /// RecDirIterState - Keeps state for the recursive_directory_iterator. It is + /// reference counted in order to preserve InputIterator semantics on copy. + struct RecDirIterState : public RefCountedBase { + RecDirIterState() + : Level(0) + , HasNoPushRequest(false) {} + + std::stack > Stack; + uint16_t Level; + bool HasNoPushRequest; + }; +} + /// recursive_directory_iterator - Same as directory_iterator except for it /// recurses down into child directories. class recursive_directory_iterator { - uint16_t Level; - bool HasNoPushRequest; - // implementation directory iterator status + IntrusiveRefCntPtr State; public: - explicit recursive_directory_iterator(const Twine &path, error_code &ec); + recursive_directory_iterator() {} + explicit recursive_directory_iterator(const Twine &path, error_code &ec) + : State(new detail::RecDirIterState) { + State->Stack.push(directory_iterator(path, ec)); + if (State->Stack.top() == directory_iterator()) + State.reset(); + } // No operator++ because we need error_code. - directory_iterator &increment(error_code &ec); + recursive_directory_iterator &increment(error_code &ec) { + static const directory_iterator end_itr; + + if (State->HasNoPushRequest) + State->HasNoPushRequest = false; + else { + file_status st; + if ((ec = State->Stack.top()->status(st))) return *this; + if (is_directory(st)) { + State->Stack.push(directory_iterator(*State->Stack.top(), ec)); + if (ec) return *this; + if (State->Stack.top() != end_itr) { + ++State->Level; + return *this; + } + State->Stack.pop(); + } + } + + while (!State->Stack.empty() + && State->Stack.top().increment(ec) == end_itr) { + State->Stack.pop(); + --State->Level; + } + + // Check if we are done. If so, create an end iterator. + if (State->Stack.empty()) + State.reset(); + + return *this; + } - const directory_entry &operator*() const; - const directory_entry *operator->() const; + const directory_entry &operator*() const { return *State->Stack.top(); }; + const directory_entry *operator->() const { return &*State->Stack.top(); }; // observers - /// Gets the current level. path is at level 0. - int level() const; + /// Gets the current level. Starting path is at level 0. + int level() const { return State->Level; } + /// Returns true if no_push has been called for this directory_entry. - bool no_push_request() const; + bool no_push_request() const { return State->HasNoPushRequest; } // modifiers /// Goes up one level if Level > 0. - void pop(); + void pop() { + assert(State && "Cannot pop and end itertor!"); + assert(State->Level > 0 && "Cannot pop an iterator with level < 1"); + + static const directory_iterator end_itr; + error_code ec; + do { + if (ec) + report_fatal_error("Error incrementing directory iterator."); + State->Stack.pop(); + --State->Level; + } while (!State->Stack.empty() + && State->Stack.top().increment(ec) == end_itr); + + // Check if we are done. If so, create an end iterator. + if (State->Stack.empty()) + State.reset(); + } + /// Does not go down into the current directory_entry. - void no_push(); + void no_push() { State->HasNoPushRequest = true; } + bool operator==(const recursive_directory_iterator &RHS) const { + return State == RHS.State; + } + + bool operator!=(const recursive_directory_iterator &RHS) const { + return !(*this == RHS); + } // Other members as required by // C++ Std, 24.1.1 Input iterators [input.iterators] }; diff --git a/lib/Support/Unix/PathV2.inc b/lib/Support/Unix/PathV2.inc index bbbc344661b..7477b4f2a08 100644 --- a/lib/Support/Unix/PathV2.inc +++ b/lib/Support/Unix/PathV2.inc @@ -439,7 +439,8 @@ rety_open_create: return success; } -error_code directory_iterator_construct(directory_iterator &it, StringRef path){ +error_code detail::directory_iterator_construct(detail::DirIterState &it, + StringRef path){ SmallString<128> path_null(path); DIR *directory = ::opendir(path_null.c_str()); if (directory == 0) @@ -452,7 +453,7 @@ error_code directory_iterator_construct(directory_iterator &it, StringRef path){ return directory_iterator_increment(it); } -error_code directory_iterator_destruct(directory_iterator& it) { +error_code detail::directory_iterator_destruct(detail::DirIterState &it) { if (it.IterationHandle) ::closedir(reinterpret_cast(it.IterationHandle)); it.IterationHandle = 0; @@ -460,7 +461,7 @@ error_code directory_iterator_destruct(directory_iterator& it) { return success; } -error_code directory_iterator_increment(directory_iterator& it) { +error_code detail::directory_iterator_increment(detail::DirIterState &it) { errno = 0; dirent *cur_dir = ::readdir(reinterpret_cast(it.IterationHandle)); if (cur_dir == 0 && errno != 0) { diff --git a/lib/Support/Windows/PathV2.inc b/lib/Support/Windows/PathV2.inc index bc597b2dcc8..3872512e4fa 100644 --- a/lib/Support/Windows/PathV2.inc +++ b/lib/Support/Windows/PathV2.inc @@ -535,7 +535,7 @@ error_code unique_file(const Twine &model, int &result_fd, if (makeAbsolute) { // Make model absolute by prepending a temp directory if it's not already. bool absolute = path::is_absolute(m); - + if (!absolute) { SmallVector temp_dir; if (error_code ec = TempDir(temp_dir)) return ec; @@ -691,7 +691,8 @@ error_code get_magic(const Twine &path, uint32_t len, return success; } -error_code directory_iterator_construct(directory_iterator &it, StringRef path){ +error_code detail::directory_iterator_construct(detail::DirIterState &it, + StringRef path){ SmallVector path_utf16; if (error_code ec = UTF8ToUTF16(path, @@ -722,7 +723,7 @@ error_code directory_iterator_construct(directory_iterator &it, StringRef path){ error_code ec = windows_error(::GetLastError()); // Check for end. if (ec == windows_error::no_more_files) - return directory_iterator_destruct(it); + return detail::directory_iterator_destruct(it); return ec; } else FilenameLen = ::wcslen(FirstFind.cFileName); @@ -742,7 +743,7 @@ error_code directory_iterator_construct(directory_iterator &it, StringRef path){ return success; } -error_code directory_iterator_destruct(directory_iterator& it) { +error_code detail::directory_iterator_destruct(detail::DirIterState &it) { if (it.IterationHandle != 0) // Closes the handle if it's valid. ScopedFindHandle close(HANDLE(it.IterationHandle)); @@ -751,13 +752,13 @@ error_code directory_iterator_destruct(directory_iterator& it) { return success; } -error_code directory_iterator_increment(directory_iterator& it) { +error_code detail::directory_iterator_increment(detail::DirIterState &it) { WIN32_FIND_DATAW FindData; if (!::FindNextFileW(HANDLE(it.IterationHandle), &FindData)) { error_code ec = windows_error(::GetLastError()); // Check for end. if (ec == windows_error::no_more_files) - return directory_iterator_destruct(it); + return detail::directory_iterator_destruct(it); return ec; } diff --git a/unittests/Support/Path.cpp b/unittests/Support/Path.cpp index 60d08bc92db..6d4dc4c9ab7 100644 --- a/unittests/Support/Path.cpp +++ b/unittests/Support/Path.cpp @@ -223,6 +223,57 @@ TEST_F(FileSystemTest, DirectoryIteration) { error_code ec; for (fs::directory_iterator i(".", ec), e; i != e; i.increment(ec)) ASSERT_NO_ERROR(ec); + + // Create a known hierarchy to recurse over. + bool existed; + ASSERT_NO_ERROR(fs::create_directories(Twine(TestDirectory) + + "/recursive/a0/aa1", existed)); + ASSERT_NO_ERROR(fs::create_directories(Twine(TestDirectory) + + "/recursive/a0/ab1", existed)); + ASSERT_NO_ERROR(fs::create_directories(Twine(TestDirectory) + + "/recursive/dontlookhere/da1", existed)); + ASSERT_NO_ERROR(fs::create_directories(Twine(TestDirectory) + + "/recursive/z0/za1", existed)); + ASSERT_NO_ERROR(fs::create_directories(Twine(TestDirectory) + + "/recursive/pop/p1", existed)); + typedef std::vector v_t; + v_t visited; + for (fs::recursive_directory_iterator i(Twine(TestDirectory) + + "/recursive", ec), e; i != e; i.increment(ec)){ + ASSERT_NO_ERROR(ec); + if (path::filename(i->path()) == "dontlookhere") + i.no_push(); + if (path::filename(i->path()) == "p1") + i.pop(); + visited.push_back(path::filename(i->path())); + } + v_t::const_iterator a0 = std::find(visited.begin(), visited.end(), "a0"); + v_t::const_iterator aa1 = std::find(visited.begin(), visited.end(), "aa1"); + v_t::const_iterator ab1 = std::find(visited.begin(), visited.end(), "ab1"); + v_t::const_iterator dontlookhere = std::find(visited.begin(), visited.end(), + "dontlookhere"); + v_t::const_iterator da1 = std::find(visited.begin(), visited.end(), "da1"); + v_t::const_iterator z0 = std::find(visited.begin(), visited.end(), "z0"); + v_t::const_iterator za1 = std::find(visited.begin(), visited.end(), "za1"); + v_t::const_iterator pop = std::find(visited.begin(), visited.end(), "pop"); + v_t::const_iterator p1 = std::find(visited.begin(), visited.end(), "p1"); + + // Make sure that each path was visited correctly. + ASSERT_NE(a0, visited.end()); + ASSERT_NE(aa1, visited.end()); + ASSERT_NE(ab1, visited.end()); + ASSERT_NE(dontlookhere, visited.end()); + ASSERT_EQ(da1, visited.end()); // Not visited. + ASSERT_NE(z0, visited.end()); + ASSERT_NE(za1, visited.end()); + ASSERT_NE(pop, visited.end()); + ASSERT_EQ(p1, visited.end()); // Not visited. + + // Make sure that parents were visited before children. No other ordering + // guarantees can be made across siblings. + ASSERT_LT(a0, aa1); + ASSERT_LT(a0, ab1); + ASSERT_LT(z0, za1); } TEST_F(FileSystemTest, Magic) { -- 2.34.1