aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--libbutl/filesystem.cxx491
-rw-r--r--libbutl/filesystem.hxx42
-rw-r--r--tests/wildcard/driver.cxx55
3 files changed, 447 insertions, 141 deletions
diff --git a/libbutl/filesystem.cxx b/libbutl/filesystem.cxx
index 18b4d22..3002c93 100644
--- a/libbutl/filesystem.cxx
+++ b/libbutl/filesystem.cxx
@@ -1097,6 +1097,192 @@ namespace butl
return match (pattern.begin (), pi.base (), name.begin (), ni.base ());
}
+ // Search for paths matching the pattern and call the specified function for
+ // each matching path. Return false if the underlying func() call returns
+ // false. Otherwise the function conforms to the path_search() description.
+ //
+ // Note that the access to the traversed directory tree (real or virtual) is
+ // performed through the provided filesystem object.
+ //
+ static const string any_dir ("*/");
+
+ template <typename FS>
+ static bool
+ search (
+ path pattern,
+ dir_path pattern_dir,
+ bool follow_symlinks,
+ const function<bool (path&&, const string& pattern, bool interm)>& func,
+ FS& filesystem)
+ {
+ // Fast-forward the leftmost pattern non-wildcard components. So, for
+ // example, search for foo/f* in /bar/ becomes search for f* in /bar/foo/.
+ //
+ {
+ auto b (pattern.begin ());
+ auto e (pattern.end ());
+ auto i (b);
+ for (; i != e && (*i).find_first_of ("*?") == string::npos; ++i) ;
+
+ // If the pattern has no wildcards then we reduce to checking for the
+ // filesystem entry existence. It matches if exists and is of the proper
+ // type.
+ //
+ if (i == e)
+ {
+ path p (pattern_dir / pattern);
+ auto pe (filesystem.path_entry (p, follow_symlinks));
+
+ if (pe.first &&
+ ((pe.second.type == entry_type::directory) == p.to_directory ()))
+ return func (move (p), string (), false);
+
+ return true;
+ }
+ else if (i != b) // There are non-wildcard components, so fast-forward.
+ {
+ path p (b, i);
+ pattern = pattern.leaf (p);
+ pattern_dir /= path_cast<dir_path> (move (p));
+ }
+ }
+
+ assert (!pattern.empty ());
+
+ // The pattern leftmost component. Will use it to match the start directory
+ // sub-entries.
+ //
+ path pc (pattern.begin (), ++pattern.begin ());
+ string pcr (pc.representation ());
+
+ // Note that if the pattern has multiple components (is not a simple path),
+ // then the leftmost one has a trailing separator, and so will match
+ // sub-directories only.
+ //
+ bool simple (pattern.simple ());
+
+ // Note that we rely on "small function object" optimization here.
+ //
+ typename FS::iterator_type i (filesystem.iterator (
+ pattern_dir,
+ pcr.find ("**") != string::npos, // Recursive.
+ pcr.find ("***") != string::npos, // Self-inclusive.
+ follow_symlinks || !simple,
+ [&pattern_dir, &func] (const dir_path& p) -> bool // Preopen.
+ {
+ return func (pattern_dir / p, any_dir, true);
+ }));
+
+ // Canonicalize the pattern component collapsing consecutive stars (used to
+ // express that it is recursive) into a single one.
+ //
+ size_t j (0);
+ size_t n (pcr.size ());
+ for (size_t i (0); i < n; ++i)
+ {
+ char c (pcr[i]);
+ if (!(c == '*' && i > 0 && pcr[i - 1] == '*'))
+ pcr[j++] = c;
+ }
+
+ if (j != n)
+ pcr.resize (j);
+
+ // Note that the callback function can be called for the same directory
+ // twice: first time as intermediate match from iterator's preopen() call,
+ // and then, if the first call succeed, from the iterating loop (possibly
+ // as the final match).
+ //
+ path p;
+ while (i.next (p))
+ {
+ // Skip sub-entry if its name doesn't match the pattern leftmost
+ // component.
+ //
+ // Matching the directory we are iterating through (as for a pattern
+ // component containing ***) is a bit tricky. This directory is
+ // represented by the iterator as an empty path, and so we need to
+ // compute it (the leaf would actually be enough) for matching. This
+ // leaf can be acquired from the start_dir / pattern_dir. We don't expect
+ // this path to be empty, as the filesystem object must replace an empty
+ // start directory with the current one. This is the case when we search
+ // in the current directory (start_dir is empty) with a pattern that
+ // starts with *** wildcard (for example f***/bar). Note that this will
+ // be the only case per path_search() as the next time pattern_dir will
+ // not be empty.
+ //
+ const path& se (!p.empty ()
+ ? p
+ : path_cast<path> (!pattern_dir.empty ()
+ ? pattern_dir
+ : filesystem.start_dir ()));
+
+ if (!path_match (pcr, se.leaf ().representation ()))
+ continue;
+
+ // If the callback function returns false, then we stop the entire search
+ // for the final match, or do not search below the path for the
+ // intermediate one.
+ //
+ if (!func (pattern_dir / p, pcr, !simple))
+ {
+ if (simple) // Final match.
+ return false;
+ else
+ continue;
+ }
+
+ // If the pattern is not a simple one, and it's leftmost component
+ // matches the sub-entry, then the sub-entry is a directory (see the note
+ // above), and we search in it using the trailing part of the pattern.
+ //
+ if (!simple && !search (pattern.leaf (pc),
+ pattern_dir / path_cast<dir_path> (move (p)),
+ follow_symlinks,
+ func,
+ filesystem))
+ return false;
+ }
+
+ return true;
+ }
+
+ // Path search implementations.
+ //
+ static const dir_path empty_dir;
+
+ using preopen = std::function<bool (const dir_path&)>;
+
+ // Base for filesystem (see above) implementations.
+ //
+ // Don't copy start directory. It is expected to exist till the end of the
+ // object lifetime.
+ //
+ class filesystem_base
+ {
+ protected:
+ filesystem_base (const dir_path& start): start_ (start) {}
+
+ public:
+ const dir_path&
+ start_dir ()
+ {
+ if (!start_.empty ())
+ return start_;
+
+ if (current_.empty ())
+ current_ = dir_path::current_directory ();
+
+ return current_;
+ }
+
+ protected:
+ const dir_path& start_;
+ dir_path current_;
+ };
+
+ // Search path in the real filesystem.
+ //
// Iterate over directory sub-entries, recursively and including itself if
// requested. Note that recursive iterating goes depth-first which make
// sense for the cleanup use cases (@@ maybe this should be controllable
@@ -1109,8 +1295,6 @@ namespace butl
// Note that iterating over non-existent directory is not en error. The
// subsequent next() call returns false for such a directory.
//
- using preopen = std::function<bool (const dir_path&)>;
-
class recursive_dir_iterator
{
public:
@@ -1128,10 +1312,11 @@ namespace butl
open (dir_path (), self_);
}
- // Non-copyable, non-movable type.
+ // Move constructible-only, non-assignable type.
//
recursive_dir_iterator (const recursive_dir_iterator&) = delete;
recursive_dir_iterator& operator= (const recursive_dir_iterator&) = delete;
+ recursive_dir_iterator (recursive_dir_iterator&&) = default;
// Return false if no more entries left. Otherwise save the next entry path
// and return true. The path is relative against the directory being
@@ -1235,165 +1420,207 @@ namespace butl
small_vector<pair<dir_iterator, dir_path>, 1> iters_;
};
- // Search for paths matching the pattern and call the specified function for
- // each matching path. Return false if the underlying func() call returns
- // false. Otherwise the function conforms to the path_search() description.
+ // Provide an access to the real filesystem.
//
- static const string any_dir ("*/");
-
- static bool
- search (
- path pattern,
- dir_path pattern_dir,
- const dir_path start_dir,
- bool follow_symlinks,
- const function<bool (path&&, const string& pattern, bool interm)>& func)
+ class real_filesystem: public filesystem_base
{
- // Fast-forward the leftmost pattern non-wildcard components. So, for
- // example, search for foo/f* in /bar/ becomes search for f* in /bar/foo/.
- //
- {
- auto b (pattern.begin ());
- auto e (pattern.end ());
- auto i (b);
- for (; i != e && (*i).find_first_of ("*?") == string::npos; ++i) ;
+ public:
+ using iterator_type = recursive_dir_iterator;
- // If the pattern has no wildcards then we reduce to checking for the
- // filesystem entry existence. It matches if exists and is of the proper
- // type.
- //
- if (i == e)
- {
- path p (pattern_dir / pattern);
- auto pe (path_entry (start_dir / p, true));
+ real_filesystem (const dir_path& start): filesystem_base (start) {}
- if (pe.first &&
- ((pe.second.type == entry_type::directory) == p.to_directory ()))
- return func (move (p), string (), false);
+ pair<bool, entry_stat>
+ path_entry (const path& p, bool follow_symlinks) const
+ {
+ return butl::path_entry (start_ / p, follow_symlinks);
+ }
- return true;
- }
- else if (i != b) // There are non-wildcard components, so fast-forward.
- {
- path p (b, i);
- pattern = pattern.leaf (p);
- pattern_dir /= path_cast<dir_path> (move (p));
- }
+ iterator_type
+ iterator (const dir_path& p,
+ bool recursive,
+ bool self,
+ bool follow_symlinks,
+ preopen po) const
+ {
+ return iterator_type (start_ / p, recursive, self, follow_symlinks, po);
}
+ };
- assert (!pattern.empty ());
+ void
+ path_search (
+ const path& pattern,
+ const function<bool (path&&, const string& pattern, bool interm)>& func,
+ const dir_path& start,
+ bool follow_symlinks)
+ {
+ real_filesystem fs (pattern.relative () ? start : empty_dir);
+ search (pattern, dir_path (), follow_symlinks, func, fs);
+ }
- // The pattern leftmost component. Will use it to match the start directory
- // sub-entries.
- //
- path pc (pattern.begin (), ++pattern.begin ());
- string pcr (pc.representation ());
+ // Search path in the directory tree represented by a path.
+ //
+ // Iterate over path prefixes, as recursive_dir_iterator (see above) would
+ // iterate over the real directory tree.
+ //
+ class path_iterator
+ {
+ public:
+ path_iterator (path p, bool recursive, bool self, preopen po)
+ : path_ (move (p)),
+ recursive_ (recursive),
+ self_ (self),
+ preopen_ (move (po)),
+ iter_ (path_.begin ())
+ {
+ open (dir_path (), self_);
+ }
- // Note that if the pattern has multiple components (is not a simple path),
- // then the leftmost one has a trailing separator, and so will match
- // sub-directories only.
+ // Move constructible-only, non-assignable type.
//
- bool simple (pattern.simple ());
+ path_iterator (const path_iterator&) = delete;
+ path_iterator& operator= (const path_iterator&) = delete;
+ path_iterator (path_iterator&&) = default;
- // Note that we rely on "small function object" optimization here.
+ // Return false if no more entries left. Otherwise save the next entry path
+ // and return true.
//
- recursive_dir_iterator i (
- start_dir / pattern_dir,
- pcr.find ("**") != string::npos, // Recursive.
- pcr.find ("***") != string::npos, // Self-inclusive.
- follow_symlinks,
- [&pattern_dir, &func] (const dir_path& p) -> bool // Preopen.
+ bool
+ next (path& p)
+ {
+ if (iter_ == path_.begin ())
{
- return func (pattern_dir / p, any_dir, true);
- });
+ if (!self_)
+ return false;
- // Canonicalize the pattern component collapsing consecutive stars (used to
- // express that it is recursive) into a single one.
- //
- size_t j (0);
- size_t n (pcr.size ());
- for (size_t i (0); i < n; ++i)
- {
- char c (pcr[i]);
- if (!(c == '*' && i > 0 && pcr[i - 1] == '*'))
- pcr[j++] = c;
- }
+ p = path ();
+ self_ = false; // To bail out the next time.
+ return true;
+ }
- if (j != n)
- pcr.resize (j);
+ path pe (path_.begin (), iter_);
+ if (recursive_ && pe.to_directory ())
+ {
+ open (path_cast<dir_path> (pe), true);
+ return next (p);
+ }
- // Note that the callback function can be called for the same directory
- // twice: first time as intermediate match from iterator's preopen() call,
- // and then, if the first call succeed, from the iterating loop (possibly
- // as the final match).
- //
- path p;
- while (i.next (p))
+ --iter_; // Return one level up.
+
+ p = move (pe);
+ return true;
+ }
+
+ private:
+ void
+ open (const dir_path& p, bool preopen)
{
- // Skip sub-entry if its name doesn't match the pattern leftmost
- // component.
+ // If preopen_() returns false, then the directory will not be
+ // traversed (as we reset the recursive flag) but still be returned by
+ // the next() call as a sub-entry.
//
- // Matching the directory we are iterating through (as for a pattern
- // component containing ***) is a bit tricky. This directory is
- // represented by the iterator as an empty path, and so we need to
- // compute it (the leaf would actually be enough) for matching. This
- // leaf can be aquired from the pattern_dir / start_dir path except the
- // case when both directories are empty. This is the case when we search
- // in the current directory (start_dir is empty) with a pattern that
- // starts with *** wildcard (for example f***/bar). All we can do here is
- // to fallback to path::current_directory() call. Note that this will be
- // the only call per path_search() as the next time pattern_dir will not
- // be empty.
+ if (preopen && !preopen_ (p))
+ recursive_ = false;
+ else if (iter_ != path_.end ())
+ ++iter_;
+
+ // If the rightmost component is reached, then all the directories were
+ // traversed, so we reset the recursive flag.
//
- const path& se (!p.empty ()
- ? p
- : path_cast<path> (!pattern_dir.empty ()
- ? pattern_dir
- : !start_dir.empty ()
- ? start_dir
- : path::current_directory ()));
+ if (iter_ == path_.end ())
+ recursive_ = false;
+ }
- if (!path_match (pcr, se.leaf ().representation ()))
- continue;
+ private:
+ path path_;
+ bool recursive_;
+ bool self_;
+ preopen preopen_;
+ path::iterator iter_;
+ };
- // If the callback function returns false, then we stop the entire search
- // for the final match, or do not search below the path for the
- // intermediate one.
- //
- if (!func (pattern_dir / p, pcr, !simple))
- {
- if (simple) // Final match.
- return false;
- else
- continue;
- }
+ // Provide an access to a directory tree, that is represented by the path.
+ //
+ // Note that symlinks are meaningless for this filesystem.
+ //
+ class path_filesystem: public filesystem_base
+ {
+ public:
+ using iterator_type = path_iterator;
- // If the pattern is not a simple one, and it's leftmost component
- // matches the sub-entry, then the sub-entry is a directory (see the note
- // above), and we search in it using the trailing part of the pattern.
+ path_filesystem (const dir_path& start, const path& p)
+ : filesystem_base (start),
+ path_ (p) {}
+
+ pair<bool, entry_stat>
+ path_entry (const path& p, bool /*follow_symlinks*/) const
+ {
+ // Note that paths are not required to be normalized, so we just check
+ // that one path is a literal prefix of the other one.
//
- if (!simple && !search (pattern.leaf (pc),
- pattern_dir / path_cast<dir_path> (move (p)),
- start_dir,
- follow_symlinks,
- func))
- return false;
+ if (!path_.sub (p))
+ return make_pair (false, entry_stat {entry_type::unknown, 0});
+
+ entry_type t (p == path_ && !p.to_directory ()
+ ? entry_type::regular
+ : entry_type::directory);
+
+ return make_pair (true, entry_stat {t, 0});
}
- return true;
- }
+ iterator_type
+ iterator (const dir_path& p,
+ bool recursive,
+ bool self,
+ bool /*follow_symlinks*/,
+ preopen po) const
+ {
+ assert (path_.sub (p));
+ return iterator_type (path_.leaf (p), recursive, self, po);
+ }
+
+ private:
+ const path& path_;
+ };
void
path_search (
const path& pattern,
+ const path& entry,
const function<bool (path&&, const string& pattern, bool interm)>& func,
- const dir_path& start,
- bool follow_symlinks)
+ const dir_path& start)
+ {
+ path_filesystem fs (pattern.relative () ? start : empty_dir, entry);
+ search (pattern, dir_path (), true, func, fs);
+ }
+
+ bool
+ path_match (const path& pattern, const path& entry, const dir_path& start)
{
- search (pattern,
- dir_path (),
- pattern.relative () ? start : dir_path (),
- follow_symlinks,
- func);
+ bool r (false);
+
+ auto match = [&entry, &r] (path&& p, const std::string&, bool interim)
+ {
+ if (p == entry)
+ {
+ // If we found the entry (possibly through one of the recursive
+ // components) no need to search further.
+ //
+ if (!interim)
+ {
+ r = true;
+ return false;
+ }
+ else
+ // For self-matching the callback is first called in the interim
+ // mode (through the preopen function) with an empty path.
+ //
+ assert (p.empty ());
+ }
+
+ return true;
+ };
+
+ path_search (pattern, entry, match, start);
+ return r;
}
}
diff --git a/libbutl/filesystem.hxx b/libbutl/filesystem.hxx
index 6ea7d2c..b4f8d96 100644
--- a/libbutl/filesystem.hxx
+++ b/libbutl/filesystem.hxx
@@ -489,6 +489,10 @@ namespace butl
// Wildcard pattern match and search (aka glob).
//
+ // Currently the following wildcard characters are supported:
+ //
+ // * - match any number of characters (including zero)
+ // ? - match any single character
// Return true if name matches pattern. Both must be single path components,
// possibly with a trailing directory separator to indicate a directory.
@@ -498,14 +502,19 @@ namespace butl
// different). Otherwise, it only matches a non-directory name (no trailing
// directory separator).
//
- // Currently the following wildcard characters are supported:
- //
- // * - match any number of characters (including zero)
- // ? - match any single character
- //
LIBBUTL_EXPORT bool
path_match (const std::string& pattern, const std::string& name);
+ // Return true if path entry matches pattern. Note that the match is
+ // performed literally, with no paths normalization being performed. The
+ // start directory is used if the first pattern component is a self-matching
+ // wildcard (see below for the start directory and wildcard semantics).
+ //
+ LIBBUTL_EXPORT bool
+ path_match (const path& pattern,
+ const path& entry,
+ const dir_path& start = dir_path ());
+
// Search for paths matching the pattern calling the specified function for
// each matching path (see below for details).
//
@@ -521,7 +530,10 @@ namespace butl
// path_search() also recognizes the ** and *** wildcard sequences. If a
// path component contains **, then it is matched just like * but in all the
// subdirectories, recursively. The *** wildcard behaves like ** but also
- // matches the start directory itself.
+ // matches the start directory itself. Note that if the first pattern
+ // component contains ***, then the start directory must be empty or be
+ // terminated with a "meaningful" component (e.g., probably not '.' or
+ // '..').
//
// So, for example, foo/bar-**.txt will return all the files matching the
// bar-*.txt pattern in all the subdirectoris of foo/. And foo/f***/ will
@@ -567,6 +579,12 @@ namespace butl
// (a/b/, b*/, true)
// (a/b/c/, c*/, false)
//
+ // Symlinks are not followed if the follow_symlinks argument is false. This
+ // rule is only applied for symlinks that are matched against the rightmost
+ // component of the pattern. In particular, this mean that such symlinks will
+ // never match a directory pattern, and some results can be missing for the
+ // recursive rightmost component.
+ //
// Note that recursive iterating through directories currently goes
// depth-first which make sense for the cleanup use cases. In future we may
// want to make it controllable.
@@ -578,6 +596,18 @@ namespace butl
bool interm)>&,
const dir_path& start = dir_path (),
bool follow_symlinks = true);
+
+ // Same as above, but behaves as if the directory tree being searched
+ // through contains only the specified entry. The start directory is used if
+ // the first pattern component is a self-matching wildcard (see above).
+ //
+ LIBBUTL_EXPORT void
+ path_search (const path& pattern,
+ const path& entry,
+ const std::function<bool (path&&,
+ const std::string& pattern,
+ bool interm)>&,
+ const dir_path& start = dir_path ());
}
#include <libbutl/filesystem.ixx>
diff --git a/tests/wildcard/driver.cxx b/tests/wildcard/driver.cxx
index 2397fc8..1e600f6 100644
--- a/tests/wildcard/driver.cxx
+++ b/tests/wildcard/driver.cxx
@@ -2,6 +2,7 @@
// copyright : Copyright (c) 2014-2017 Code Synthesis Ltd
// license : MIT; see accompanying LICENSE file
+#include <map>
#include <string>
#include <vector>
#include <cassert>
@@ -90,8 +91,11 @@ try
assert (i == argc); // All args parsed,
vector<path> paths;
- auto add =
- [&paths, &start] (path&& p, const std::string& pt, bool interim) -> bool
+ map<path, size_t> path_count;
+
+ auto add = [&paths, &path_count, &start] (path&& p,
+ const string& pt,
+ bool interim)
{
bool pd (!pt.empty () && pt[0] == '.'); // Dot-started pattern.
@@ -114,13 +118,58 @@ try
return !skip;
if (!skip)
- paths.emplace_back (move (p.canonicalize ()));
+ {
+ p.canonicalize ();
+
+ auto i (path_count.find (p));
+ if (i == path_count.end ())
+ path_count[p] = 1;
+ else
+ ++(i->second);
+
+ paths.emplace_back (move (p));
+ }
return true;
};
path_search (pattern, add, start);
+ // Test search in the directory tree represented by the path.
+ //
+ for (const auto& p: path_count)
+ {
+ // Will match multiple times if the pattern contains several recursive
+ // components.
+ //
+ size_t match_count (0);
+
+ auto check = [&p, &match_count] (path&& pe, const string&, bool interim)
+ {
+ if (pe == p.first)
+ {
+ if (!interim)
+ ++match_count;
+ else
+ // For self-matching the callback is first called in the interim
+ // mode (through the preopen function) with an empty path.
+ //
+ assert (pe.empty ());
+ }
+
+ return true;
+ };
+
+ path_search (pattern, p.first, check, start);
+ assert (match_count == p.second);
+
+ // Test path match.
+ //
+ assert (path_match (pattern, p.first, start));
+ }
+
+ // Print the found paths.
+ //
if (sort)
std::sort (paths.begin (), paths.end ());