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
diff --git a/include/llvm/ADT/IntrusiveRefCntPtr.h b/include/llvm/ADT/IntrusiveRefCntPtr.h
index 8757f00..106daf4 100644
--- a/include/llvm/ADT/IntrusiveRefCntPtr.h
+++ b/include/llvm/ADT/IntrusiveRefCntPtr.h
@@ -156,7 +156,12 @@
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 a868e5f..42e61dc 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 <ctime>
#include <iterator>
+#include <stack>
#include <string>
namespace llvm {
@@ -479,76 +482,171 @@
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> {
+ 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<detail::DirIterState> 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));
+ }
+
+ 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() : IterationHandle(0) {}
-
- ~directory_iterator() {
- directory_iterator_destruct(*this);
- }
+ 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> {
+ RecDirIterState()
+ : Level(0)
+ , HasNoPushRequest(false) {}
+
+ std::stack<directory_iterator, std::vector<directory_iterator> > 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<detail::RecDirIterState> 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;
- const directory_entry &operator*() const;
- const directory_entry *operator->() const;
+ 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 { 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();
- /// Does not go down into the current directory_entry.
- void no_push();
+ 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() { 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 bbbc344..7477b4f 100644
--- a/lib/Support/Unix/PathV2.inc
+++ b/lib/Support/Unix/PathV2.inc
@@ -439,7 +439,8 @@
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 @@
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<DIR *>(it.IterationHandle));
it.IterationHandle = 0;
@@ -460,7 +461,7 @@
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<DIR *>(it.IterationHandle));
if (cur_dir == 0 && errno != 0) {
diff --git a/lib/Support/Windows/PathV2.inc b/lib/Support/Windows/PathV2.inc
index bc597b2..3872512 100644
--- a/lib/Support/Windows/PathV2.inc
+++ b/lib/Support/Windows/PathV2.inc
@@ -535,7 +535,7 @@
if (makeAbsolute) {
// Make model absolute by prepending a temp directory if it's not already.
bool absolute = path::is_absolute(m);
-
+
if (!absolute) {
SmallVector<wchar_t, 64> temp_dir;
if (error_code ec = TempDir(temp_dir)) return ec;
@@ -691,7 +691,8 @@
return success;
}
-error_code directory_iterator_construct(directory_iterator &it, StringRef path){
+error_code detail::directory_iterator_construct(detail::DirIterState &it,
+ StringRef path){
SmallVector<wchar_t, 128> path_utf16;
if (error_code ec = UTF8ToUTF16(path,
@@ -722,7 +723,7 @@
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 @@
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 @@
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 60d08bc..6d4dc4c 100644
--- a/unittests/Support/Path.cpp
+++ b/unittests/Support/Path.cpp
@@ -223,6 +223,57 @@
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<std::string> 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) {