diff options
| -rw-r--r-- | butl/filesystem | 53 | ||||
| -rw-r--r-- | butl/filesystem.cxx | 369 | ||||
| -rw-r--r-- | butl/path | 2 | ||||
| -rw-r--r-- | tests/buildfile | 3 | ||||
| -rw-r--r-- | tests/wildcard/buildfile | 7 | ||||
| -rw-r--r-- | tests/wildcard/driver.cxx | 105 | ||||
| -rw-r--r-- | tests/wildcard/testscript | 378 |
7 files changed, 915 insertions, 2 deletions
diff --git a/butl/filesystem b/butl/filesystem index ef715c6..a125dab 100644 --- a/butl/filesystem +++ b/butl/filesystem @@ -24,6 +24,7 @@ #include <cstdint> // uint16_t #include <utility> // move(), pair #include <iterator> +#include <functional> #include <butl/export> @@ -396,6 +397,58 @@ namespace butl // inline dir_iterator begin (dir_iterator&); inline dir_iterator end (const dir_iterator&); + + // Wildcard pattern match and search (aka glob). + // + + // Return true if name matches pattern. Both must be single path components, + // possibly with a trailing directory separator to indicate a directory. + // + // If the pattern ends with a directory separator, then it only matches a + // directory name (i.e., ends with a directory separator, but potentially + // 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); + + // Search for paths matching the pattern calling the specified function for + // each matching path. Stop the search if the function returns false. + // + // If the pattern is relative, then search in the start directory. If the + // start directory is empty, then search in the current working directory. + // Searching in non-existent directories is not an error. Throw + // std::system_error in case of a failure (insufficient permissions, etc). + // + // The pattern may contain multiple components that include wildcards. On + // Windows the drive letter may not be a wildcard. + // + // In addition to the wildcard characters listed in path_match(), + // 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. + // + // 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 + // return all the subdirectories matching the f*/ pattern plus foo/ itself. + // + // Note that having multiple recursive components in the pattern we can end + // up with calling func() multiple times (once per such a component) for the + // same path. For example the search with pattern f***/b**/ starting in + // directory foo, that has the foo/fox/box/ structure, will result in + // calling func(foo/fox/box/) twice: first time for being a child of fox/, + // second time for being a child of foo/. + // + LIBBUTL_EXPORT void + path_search (const path& pattern, + const std::function<bool (path&&)>&, + const dir_path& start = dir_path ()); } #include <butl/filesystem.ixx> diff --git a/butl/filesystem.cxx b/butl/filesystem.cxx index e7e54a8..1553324 100644 --- a/butl/filesystem.cxx +++ b/butl/filesystem.cxx @@ -25,10 +25,16 @@ #include <errno.h> // errno, E* +#include <string> +#include <vector> #include <memory> // unique_ptr +#include <utility> // pair +#include <iterator> // reverse_iterator #include <system_error> +#include <butl/path> #include <butl/fdstream> +#include <butl/small-vector> using namespace std; @@ -728,4 +734,367 @@ namespace butl } } #endif + + // Match the name [ni, ne) to the pattern [pi, pe). Ranges can be empty. + // + static bool + match (string::const_iterator pi, string::const_iterator pe, + string::const_iterator ni, string::const_iterator ne) + { + using reverse_iterator = std::reverse_iterator<string::const_iterator>; + + reverse_iterator rpi (pe); + reverse_iterator rpe (pi); + + reverse_iterator rni (ne); + reverse_iterator rne (ni); + + // Match the pattern suffix (follows the last *) to the name trailing + // characters. + // + char pc; + for (; rpi != rpe && (pc = *rpi) != '*' && rni != rne; ++rpi, ++rni) + { + if (*rni != pc && pc != '?') + return false; + } + + // If we got to the (reversed) end of the pattern (no * is encountered) + // than we are done. The success depends on if we got to the (reversed) end + // of the name as well. + // + if (rpi == rpe) + return rni == rne; + + // If we didn't reach * in the pattern then we reached the (reversed) end + // of the name. That means we have unmatched non-star characters in the + // pattern, and so match failed. + // + if (pc != '*') + { + assert (rni == rne); + return false; + } + + // Match the pattern prefix (ends with the first *) to the name leading + // characters. If they mismatch we failed. Otherwise if this is an only * + // in the pattern (matches whatever is left in the name) then we succeed, + // otherwise we perform backtracking (recursively). + // + pe = rpi.base (); + ne = rni.base (); + + // Compare the pattern and the name char by char until the name suffix or + // * is encountered in the pattern (whichever happens first). Fail if a + // char mismatches. + // + for (; (pc = *pi) != '*' && ni != ne; ++pi, ++ni) + { + if (*ni != pc && pc != '?') + return false; + } + + // If we didn't get to * in the pattern then we got to the name suffix. + // That means that the pattern has unmatched non-star characters, and so + // match failed. + // + if (pc != '*') + { + assert (ni == ne); + return false; + } + + // If * that we have reached is the last one, then it matches whatever is + // left in the name (including an empty range). + // + if (++pi == pe) + return true; + + // Perform backtracking. + // + // From now on, we will call the pattern not-yet-matched part (starting + // the leftmost * and ending the rightmost one inclusively) as pattern, and + // the name not-yet-matched part as name. + // + // Here we sequentially assume that * that starts the pattern matches the + // name leading part (staring from an empty one and iterating till the full + // name). So if, at some iteration, the pattern trailing part (that follows + // the leftmost *) matches the name trailing part, then the pattern matches + // the name. + // + bool r; + for (; !(r = match (pi, pe, ni, ne)) && ni != ne; ++ni) ; + return r; + } + + bool + path_match (const string& pattern, const string& name) + { + // Implementation notes: + // + // - This has a good potential of becoming hairy quickly so need to strive + // for an elegant way to implement this. + // + // - Most patterns will contains a single * wildcard with a prefix and/or + // suffix (e.g., *.txt, foo*, f*.txt). Something like this is not very + // common: *foo*. + // + // So it would be nice to have a clever implementation that first + // "anchors" itself with a literal prefix and/or suffix and only then + // continue with backtracking. In other words, reduce: + // + // *.txt vs foo.txt -> * vs foo + // foo* vs foo.txt -> * vs .txt + // f*.txt vs foo.txt -> * vs oo + // + + auto pi (pattern.rbegin ()); + auto pe (pattern.rend ()); + + auto ni (name.rbegin ()); + auto ne (name.rend ()); + + // The name doesn't match the pattern if it is of a different type than the + // pattern is. + // + bool pd (pi != pe && path::traits::is_separator (*pi)); + bool nd (ni != ne && path::traits::is_separator (*ni)); + + if (pd != nd) + return false; + + // Skip trailing separators if present. + // + if (pd) + { + ++pi; + ++ni; + } + + return match (pattern.begin (), pi.base (), name.begin (), ni.base ()); + } + + // 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 + // since for directory creation it won't make sense). + // + // Note that iterating over non-existent directory is not en error. The + // subsequent next() call returns false for such a directory. + // + class recursive_dir_iterator + { + public: + recursive_dir_iterator (dir_path p, bool recursive, bool self) + : recursive_ (recursive), self_ (self), start_ (p) + { + open (dir_path ()); + } + + // Non-copyable, non-movable type. + // + recursive_dir_iterator (const recursive_dir_iterator&) = delete; + recursive_dir_iterator& operator= (const recursive_dir_iterator&) = delete; + + // Return false if no more entries left. Otherwise save the next entry path + // and return true. The path is relative against the directory being + // traversed and contains a trailing separator for sub-directories. Throw + // std::system_error in case of a failure (insufficient permissions, + // dangling symlink encountered, etc). + // + bool + next (path& p) + { + if (iters_.empty ()) + return false; + + auto& i (iters_.back ()); + + // If we got to the end of directory sub-entries, then go one level up + // and return this directory path. + // + if (i.first == dir_iterator ()) + { + path d (move (i.second)); + iters_.pop_back (); + + // Return the path unless it is the last one (the directory we started + // to iterate from) and the self flag is not set. + // + if (iters_.empty () && !self_) + return false; + + p = move (d); + return true; + } + + const dir_entry& de (*i.first); + + // Append separator if a directory. Note that dir_entry::type() can + // throw. + // + path pe (de.type () == entry_type::directory + ? path_cast<dir_path> (i.second / de.path ()) + : i.second / de.path ()); + + ++i.first; + + if (recursive_ && pe.to_directory ()) + { + open (path_cast<dir_path> (move (pe))); + return next (p); + } + + p = move (pe); + return true; + } + + private: + void + open (dir_path p) + { + // We should consider a racing condition here. The directory can be + // removed before we create an iterator for it. In this case we just do + // nothing, so the directory is silently skipped. + // + try + { + dir_path d (start_ / p); + dir_iterator i (!d.empty () ? d : dir_path (".")); + iters_.emplace_back (move (i), move (p)); + } + catch (const system_error& e) + { + // Ignore non-existent directory (ENOENT or ENOTDIR). Rethrow for any + // other error. We consider ENOTDIR as a variety of removal, with a + // new filesystem entry being created afterwards. + // + int ec (e.code ().value ()); + if (ec != ENOENT && ec != ENOTDIR) + throw; + } + } + + private: + bool recursive_; + bool self_; + dir_path start_; + 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. + // + static bool + search (path pattern, dir_path pattern_dir, const dir_path start_dir, + const function<bool (path&&)>& func) + { + // 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 (path_entry (start_dir / p, true)); + + if (pe.first && + ((pe.second == entry_type::directory) == p.to_directory ())) + return func (move (p)); + + 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 ()); + + recursive_dir_iterator i ( + start_dir / pattern_dir, + pcr.find ("**") != string::npos, // Recursive. + pcr.find ("***") != string::npos); // Self-inclusive. + + 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 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. + // + const path& se (!p.empty () + ? p + : path_cast<path> (!pattern_dir.empty () + ? pattern_dir + : !start_dir.empty () + ? start_dir + : path::current_directory ())); + + if (!path_match (pcr, se.leaf ().representation ())) + continue; + + // If the pattern is a simple path then call func() for the sub-entry. + // Otherwise the sub-entry is a directory (read above), and we search in + // it using the trailing part of the pattern. + // + if (!( + simple + ? func (pattern_dir / p) + : search (pattern.leaf (pc), + pattern_dir / path_cast<dir_path> (move (p)), + start_dir, + func))) + return false; + } + + return true; + } + + void + path_search (const path& pattern, + const function<bool (path&&)>& func, + const dir_path& start) + { + search (pattern, + dir_path (), + pattern.relative () ? start : dir_path (), + func); + } } @@ -27,7 +27,7 @@ namespace butl // p -= "*/"; // leaf // p -= ".*"; // base // - // - Faster normalize() implementation. In many cases (e.g., in buil2) + // - Faster normalize() implementation. In many cases (e.g., in build2) // the path is either already normal or the difference is just slashes // (i.e., there are no '.' or '..' components). So a fast path case // might be in order. diff --git a/tests/buildfile b/tests/buildfile index 8608ed9..6f5dd03 100644 --- a/tests/buildfile +++ b/tests/buildfile @@ -4,7 +4,8 @@ d = base64/ cpfile/ dir-iterator/ fdstream/ link/ manifest-parser/ \ manifest-serializer/ manifest-roundtrip/ pager/ path/ prefix-map/ \ - process/ sha256/ small-vector/ strcase/ timestamp/ target-triplet/ + process/ sha256/ small-vector/ strcase/ timestamp/ target-triplet/ \ + wildcard/ ./: $d include $d diff --git a/tests/wildcard/buildfile b/tests/wildcard/buildfile new file mode 100644 index 0000000..7de67f4 --- /dev/null +++ b/tests/wildcard/buildfile @@ -0,0 +1,7 @@ +# file : tests/wildcard/buildfile +# copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +# license : MIT; see accompanying LICENSE file + +exe{driver}: cxx{driver} ../../butl/lib{butl} test{testscript} + +include ../../butl/ diff --git a/tests/wildcard/driver.cxx b/tests/wildcard/driver.cxx new file mode 100644 index 0000000..7df5556 --- /dev/null +++ b/tests/wildcard/driver.cxx @@ -0,0 +1,105 @@ +// file : tests/wildcard/driver.cxx -*- C++ -*- +// copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +// license : MIT; see accompanying LICENSE file + +#include <string> +#include <vector> +#include <cassert> +#include <iostream> +#include <algorithm> // sort() +#include <exception> + +#include <butl/path> +#include <butl/utility> // operator<<(ostream, exception) +#include <butl/filesystem> + +using namespace std; +using namespace butl; + +// Usage: argv[0] (-m <pattern> <name> | -s [-n] <pattern> [<dir>]) +// +// Execute actions specified by -m or -s options. Exit with code 0 if succeed, +// 1 if fail, 2 on the underlying OS error (print error description to STDERR). +// +// -m +// Match a name against the pattern. +// +// -s +// Search for paths matching the pattern in the directory specified (absent +// directory means the current one). Print the matching canonicalized paths +// to STDOUT in the ascending order. Succeed if at least one matching path +// is found. Note that this option must go first in the command line, +// +// -n +// Do not sort paths found. +// +int +main (int argc, const char* argv[]) +try +{ + assert (argc >= 2); + + string op (argv[1]); + bool match (op == "-m"); + assert (match || op == "-s"); + + if (match) + { + assert (argc == 4); + + string pattern (argv[2]); + string name (argv[3]); + return path_match (pattern, name) ? 0 : 1; + } + else + { + assert (argc >= 3); + + bool sort (true); + int i (2); + for (; i != argc; ++i) + { + string o (argv[i]); + if (o == "-n") + sort = false; + else + break; // End of options. + } + + assert (i != argc); // Still need pattern. + path pattern (argv[i++]); + + dir_path start; + if (i != argc) + start = dir_path (argv[i++]); + + assert (i == argc); // All args parsed, + + vector<path> paths; + auto add = [&paths] (path&& p) -> bool + { + paths.emplace_back (move (p.canonicalize ())); + return true; + }; + + path_search (pattern, add, start); + + if (sort) + std::sort (paths.begin (), paths.end ()); + + for (const auto& p: paths) + cout << p.representation () << endl; + + return paths.empty () ? 1 : 0; + } +} +catch (const invalid_path& e) +{ + cerr << e << ": " << e.path << endl; + return 2; +} +catch (const exception& e) +{ + cerr << e << endl; + return 2; +} diff --git a/tests/wildcard/testscript b/tests/wildcard/testscript new file mode 100644 index 0000000..bcd618f --- /dev/null +++ b/tests/wildcard/testscript @@ -0,0 +1,378 @@ +# file : tests/wildcard/testscript +# copyright : Copyright (c) 2014-2017 Code Synthesis Ltd +# license : MIT; see accompanying LICENSE file + +: path-match +: +{ + test.options = -m + + $* foo/ foo == 1 : dir-vs-file + $* foo foo/ == 1 : file-vs-dir + + : no-star + : + { + : match + : + { + $* foo/ foo/ : dir + $* foo foo : file + $* f?o foo : qmark + $* '' '' : empty + } + + : no-match + : + { + $* oo foo == 1 : name-char + $* foo oo == 1 : pattern-char + } + } + + : with-star + : + { + : no-backtracking + : + { + : match + : + { + $* * '' : empty + $* *.txt foo.txt : suffix-only + $* foo* foo.txt : prefix-only + $* f*.txt foo.txt : prefix-suffix + } + + : no-match + : + { + $* fox* foo.txt == 1 : pattern-prefix-char + $* foo* fo == 1 : short-name + } + } + + : backtracking + : + { + : match + : + { + $* ** '' : empty1 + $* *** '' : empty2 + $* f*.* f.txt : empty3 + $* f**.* f.txt : empty4 + $* f*.* foo.txt : non-empty + $* f*?* foo-txt : qmark + } + + : no-match + : + { + $* f*.* foo-txt == 1 + } + } + } +} + +: path-search +: +{ + test.options = -s + + : start + : + { + : empty + : + $* * >>/EOO + stderr + stdout + EOO + + : relative + : + mkdir -p foo/fox/bar; + $* ba*/ foo/fox >>/EOO + bar/ + EOO + + : absolute + : + : When cross-testing we can't guarantee that host absolute paths are + : recognized by the target process. + : + if ($test.target == $build.host) + { + wd = $~ + +mkdir -p foo/bar + + : dir + : + $* ba*/ "$wd/foo" >>/EOO + bar/ + EOO + + : pattern + : + $* "$wd/foo/ba*/" >>/"EOO" + $wd/foo/bar/ + EOO + } + } + + : pattern + : + { + : simple + : + { + : file + : + { + +mkdir -p foo/bar + +touch foo/baz foo/box foo/bar/bar foo/bar/fox + + : immediate + : + $* b* ../foo >>EOO + baz + box + EOO + + : recursive + : + $* ba** ../foo >>/EOO + bar/bar + baz + EOO + + : self-recursive + : + { + : start + : + $* f*** ../../foo >>/EOO + bar/fox + EOO + + : current + : + mkdir -p bar/fox; + touch bar/fox/cox; + $* c*** >>/EOO + bar/fox/cox + EOO + } + } + + : dir + : + { + +mkdir -p foo/bar/bar foo/bar/fox/ + +touch foo/baz + + : immediate + : + $* b*/ ../foo >>/EOO + bar/ + EOO + + : recursive + : + $* -n b**/ ../foo >>/EOO + bar/bar/ + bar/ + EOO + + : self-recursive + : + { + : start + : + : Note that the start dir is represented as an empty path being + : found. + : + $* f***/ ../../foo >>/EOO + + bar/fox/ + EOO + + : current + : + mkdir -p bar/cox/box/; + $* c***/ >>/EOO + + bar/cox/ + EOO + } + } + } + + : compound + : + { + : file + : + { + +mkdir -p foo fox fix/bar baz/foo/zab baz/foo/zab/baz + +touch foo/bar foo/fox fox/baz baz/foo/zab/bar + + : immediate + : + $* f*/b* .. >>/EOO + foo/bar + fox/baz + EOO + + : recursive + : + $* f**/b** .. >>/EOO + baz/foo/zab/bar + foo/bar + fox/baz + EOO + + : self-recursive + : + { + : pattern + : + $* foo/f*** ../.. >>/EOO + foo/fox + EOO + + : start + : + $* f*** ../../foo >>/EOO + fox + EOO + + : current + : + mkdir -p bar; + touch bar/cox; + $* c*** >>/EOO + bar/cox + EOO + } + } + + : dir + : + { + +mkdir -p foo/bar foo/fox/box fox/baz fix baz/foo/zab/baz + +touch fix/bar baz/foo/zab/bar + + : immediate + : + $* f*/b*/ .. >>/EOO + foo/bar/ + fox/baz/ + EOO + + : recursive + : + $* f**/b**/ .. >>/EOO + baz/foo/zab/baz/ + foo/bar/ + foo/fox/box/ + foo/fox/box/ + fox/baz/ + EOO + + : self-recursive + : + { + : pattern + : + $* foo/f***/b**/ ../.. >>/EOO + foo/bar/ + foo/fox/box/ + foo/fox/box/ + EOO + + : start + : + $* f***/b**/ ../../foo >>/EOO + bar/ + fox/box/ + fox/box/ + EOO + + : current + : + mkdir -p bar/cox/box/; + $* c***/b**/ >>/EOO + bar/ + bar/cox/box/ + bar/cox/box/ + EOO + } + } + } + + : fast-forward + : + { + +mkdir -p foo/bar/baz foo/box + +touch foo/bar/baz/fox + + : partial + : + { + wd = ../.. + + : file + : + $* foo/ba*/baz/f* $wd >>/EOO + foo/bar/baz/fox + EOO + + : dir + : + $* foo/b*/baz/ $wd >>/EOO + foo/bar/baz/ + EOO + } + + : reduce + : + { + wd = ../../.. + + : exists + : + { + : file + : + $* fo?/bar/baz/fox $wd >>/EOO + foo/bar/baz/fox + EOO + + : dir + : + $* fo?/bar/baz/ $wd >>/EOO + foo/bar/baz/ + EOO + + : parent + : + $* fo?/box/../bar/baz/fox $wd >>/EOO + foo/box/../bar/baz/fox + EOO + } + + : not-exists + : + { + $* fo?/bar/baz/foz $wd == 1 : file + $* fo?/bar/bax/ $wd == 1 : dir + $* fo?/bar/baz/fox/ $wd == 1 : not-dir + $* fo?/bix/../bar/baz/foz $wd == 1 : parent + } + } + } + } +} |