diff options
| -rw-r--r-- | libbutl/filesystem.cxx | 320 | ||||
| -rw-r--r-- | libbutl/filesystem.ixx | 127 | ||||
| -rw-r--r-- | libbutl/filesystem.mxx | 164 | ||||
| -rw-r--r-- | tests/wildcard/testscript | 70 |
4 files changed, 632 insertions, 49 deletions
diff --git a/libbutl/filesystem.cxx b/libbutl/filesystem.cxx index 80fc4d1..9769124 100644 --- a/libbutl/filesystem.cxx +++ b/libbutl/filesystem.cxx @@ -37,15 +37,16 @@ #include <cassert> #ifndef __cpp_lib_modules_ts +#include <string> #include <cstddef> #include <cstdint> #include <utility> #include <iterator> #include <functional> -#include <string> #include <vector> #include <memory> // unique_ptr +#include <algorithm> // find(), copy() #include <system_error> #endif @@ -437,7 +438,7 @@ namespace butl ur = symlink ? _rmdir (f) : _unlink (f); - // Restoring the attribute is unlikely to fail as we managed to + // Restoring the attribute is unlikely to fail since we managed to // reset it earlier. // if (ur != 0 && restore) @@ -1556,11 +1557,72 @@ namespace butl } #endif - // Match the name [ni, ne) to the pattern [pi, pe). Ranges can be empty. + // patterns + // + static inline bool + match (char c, char pc) + { +#ifndef _WIN32 + return c == pc; +#else + return lcase (c) == lcase (pc); +#endif + } + + bool + match_bracket (char c, const path_pattern_term& pt) + { + using iterator = string::const_iterator; + + assert (pt.bracket ()); + + iterator i (pt.begin + 1); // Position after '['. + iterator e (pt.end - 1); // Position at ']'. + + bool invert (*i == '!'); + if (invert) + ++i; + + bool r (false); + for (iterator b (i); i != e && !r; ++i) + { + char bc (*i); + + // If '-' is a first or last character in the bracket expression then + // match it literally and match the range otherwise. + // + if (bc == '-' && i != b && i + 1 != e) // Match the range? + { + // Note that we have already matched the range left endpoint character + // unsuccessfully (otherwise we wouldn't be here), so now we test if + // the character belongs to the (min-char, max-char] range. + // + // Also note that on Windows we match case insensitively and so can't + // just compare the character with the range endpoints. Thus, we + // fallback to matching each range character individually. + // +#ifndef _WIN32 + r = c > *(i - 1) && c <= *(i + 1); +#else + for (char bc (*(i - 1) + 1), mx (*(i + 1)); bc <= mx && !r; ++bc) + r = match (c, bc); +#endif + + ++i; // Position to the range max character. + } + else // Match against the expression character literally. + r = match (c, bc); + } + + return r != invert; + } + + // Match the name [ni, ne) to the pattern [pi, pe) that may not contain + // bracket expressions. Ranges can be empty. // static bool - match (string::const_iterator pi, string::const_iterator pe, - string::const_iterator ni, string::const_iterator ne) + match_no_brackets (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>; @@ -1576,11 +1638,7 @@ namespace butl char pc ('\0'); for (; rpi != rpe && (pc = *rpi) != '*' && rni != rne; ++rpi, ++rni) { -#ifndef _WIN32 - if (*rni != pc && pc != '?') -#else - if (lcase (*rni) != lcase (pc) && pc != '?') -#endif + if (!match (*rni, pc) && pc != '?') return false; } @@ -1592,7 +1650,7 @@ namespace butl 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 + // of the name. That means we have unmatched non-star terms in the // pattern, and so match failed. // if (pc != '*') @@ -1609,23 +1667,19 @@ namespace butl pe = rpi.base (); ne = rni.base (); - // Compare the pattern and the name char by char until the name suffix or + // Compare the pattern and the name term 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) { -#ifndef _WIN32 - if (*ni != pc && pc != '?') -#else - if (lcase (*ni) != lcase (pc) && pc != '?') -#endif + if (!match (*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. + // That means that the pattern has unmatched non-star terms, and so match + // failed. // if (pc != '*') { @@ -1652,7 +1706,94 @@ namespace butl // the name. // bool r; - for (; !(r = match (pi, pe, ni, ne)) && ni != ne; ++ni) ; + for (; !(r = match_no_brackets (pi, pe, ni, ne)) && ni != ne; ++ni) ; + return r; + } + + // Match a character against the pattern term. + // + static inline bool + match (char c, const path_pattern_term& pt) + { + switch (pt.type) + { + // Matches any character. + // + case path_pattern_term_type::star: + case path_pattern_term_type::question: return true; + + case path_pattern_term_type::bracket: + { + return match_bracket (c, pt); + } + + case path_pattern_term_type::literal: + { + return match (c, get_literal (pt)); + } + } + + assert (false); // Can't be here. + return false; + } + + // 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) + { + // If the pattern doesn't contain the bracket expressions then reduce to + // the "clever" approach (see the implementation notes below for details). + // + if (find (pi, pe, '[') == pe) + return match_no_brackets (pi, pe, ni, ne); + + // Match the pattern prefix (precedes the first *) to the name leading + // characters. + // + path_pattern_iterator ppi (pi, pe); + path_pattern_iterator ppe; + path_pattern_term pt; + + for (; ppi != ppe && !(pt = *ppi).star () && ni != ne; ++ppi, ++ni) + { + if (!match (*ni, pt)) + return false; + } + + // If we got to the end of the pattern (no * is encountered) than we are + // done. The success depends on if we got to the end of the name as well. + // + if (ppi == ppe) + return ni == ne; + + // If we didn't reach * in the pattern then we reached the end of the + // name. That means we have unmatched non-star terms in the pattern, and + // so match failed. + // + if (!pt.star ()) + { + assert (ni == ne); + return false; + } + + // If * that we have reached is the last term, then it matches whatever is + // left in the name (including an empty range). + // + if (++ppi == ppe) + return true; + + // Switch back to the string iterator and perform backtracking. + // + // From now on, we will call the pattern not-yet-matched part (starting + // the leftmost *) 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 (see match_no_brackets() for details). + // + bool r; + for (pi = ppi->begin; !(r = match (pi, pe, ni, ne)) && ni != ne; ++ni) ; return r; } @@ -1676,6 +1817,16 @@ namespace butl // foo* vs foo.txt -> * vs .txt // f*.txt vs foo.txt -> * vs oo // + // Note that this approach fails if the pattern may contain bracket + // expressions. You can't easily recognize a suffix scanning backwards + // since * semantics depends on the characters to the left: + // + // f[o*]o - * is not a wildcard + // fo*]o - * is a wildcard + // + // That's why we will start with the straightforward left-to-right + // matching and reduce to the "clever" approach when the remaining part + // of the pattern doesn't contain bracket expressions. auto pi (pattern.rbegin ()); auto pe (pattern.rend ()); @@ -1731,7 +1882,7 @@ namespace butl auto b (pattern.begin ()); auto e (pattern.end ()); auto i (b); - for (; i != e && (*i).find_first_of ("*?") == string::npos; ++i) ; + for (; i != e && !path_pattern (*i); ++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 @@ -1774,8 +1925,8 @@ namespace butl // typename FS::iterator_type i (filesystem.iterator ( pattern_dir, - pcr.find ("**") != string::npos, // Recursive. - pcr.find ("***") != string::npos, // Self-inclusive. + path_pattern_recursive (pcr), + path_pattern_self_matching (pcr), follow_symlinks || !simple, [&pattern_dir, &func] (const dir_path& p) -> bool // Preopen. { @@ -1785,17 +1936,30 @@ namespace butl // 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) + auto j (pcr.begin ()); + bool prev_star (false); + for (const path_pattern_term& t: path_pattern_iterator (pcr)) { - char c (pcr[i]); - if (!(c == '*' && i > 0 && pcr[i - 1] == '*')) - pcr[j++] = c; + // Skip the repeated star wildcard. + // + if (t.star () && prev_star) + continue; + + // Note: we only need to copy the pattern term if a star have already + // been skipped. + // + assert (j <= t.begin); + + if (j != t.begin) + copy (t.begin, t.end, j); + + j += t.size (); + + prev_star = t.star (); } - if (j != n) - pcr.resize (j); + if (j != pcr.end ()) + pcr.resize (j - pcr.begin ()); // Note that the callback function can be called for the same directory // twice: first time as intermediate match from iterator's preopen() call, @@ -1873,7 +2037,7 @@ namespace butl // static const dir_path empty_dir; - using preopen = std::function<bool (const dir_path&)>; + using preopen = function<bool (const dir_path&)>; // Base for filesystem (see above) implementations. // @@ -2005,7 +2169,7 @@ namespace butl try { // If preopen_() returns false, then the directory will not be - // traversed (as we leave iterator with end semantics) but still be + // traversed (since we leave iterator with end semantics) but still be // returned by the next() call as a sub-entry. // dir_iterator i; @@ -2171,8 +2335,8 @@ namespace butl open (const dir_path& p, bool preopen) { // 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. + // traversed (since we reset the recursive flag) but still be returned + // by the next() call as a sub-entry. // if (preopen && !preopen_ (p)) recursive_ = false; @@ -2312,7 +2476,7 @@ namespace butl { bool r (false); - auto match = [&entry, &r] (path&& p, const std::string&, bool interim) + auto match = [&entry, &r] (path&& p, const string&, bool interim) { // If we found the entry (possibly through one of the recursive // components) no need to search further. @@ -2329,4 +2493,88 @@ namespace butl path_search (pattern, entry, match, start, flags); return r; } + + // path_pattern_iterator + // + void path_pattern_iterator:: + next () + { + if (i_ == e_) + { + t_ = nullopt; // Convert the object into the end iterator. + return; + } + + auto next = [this] (path_pattern_term_type t) + { + assert (t != path_pattern_term_type::bracket); + + t_ = path_pattern_term {t, i_, i_ + 1}; + ++i_; + }; + + switch (*i_) + { + case '?': + { + next (path_pattern_term_type::question); + break; + } + case '*': + { + next (path_pattern_term_type::star); + break; + } + case '[': + { + // Try to find the bracket expression end. + // + // Note that '[' doesn't necessarily starts the bracket expression (no + // closing bracket, empty, etc). If that's the case, then we end up + // with the '[' literal terminal. + // + bool expr (false); + for (;;) // Breakout loop. + { + string::const_iterator i (i_ + 1); // Position after '['. + + if (i == e_) // Is '[' the pattern last character? + break; + + bool invert (*i == '!'); + if (invert && ++i == e_) // Is '!' the pattern last character? + break; + + // Find the bracket expression end. + // + // Note that the bracket expression may not be empty and ']' is a + // literal if it is the first expression character. + // + for (++i; i != e_ && *i != ']'; ++i) ; + + if (i == e_) // The closing bracket is not found? + break; + + expr = true; + + ++i; // Position after ']'. + + t_ = path_pattern_term {path_pattern_term_type::bracket, i_, i}; + + i_ = i; + break; + } + + // Fallback to '[' literal if it is not a bracket expression. + // + if (expr) + break; + } + // Fall through. + default: + { + next (path_pattern_term_type::literal); + } + } + } } diff --git a/libbutl/filesystem.ixx b/libbutl/filesystem.ixx index c9e3997..1be5246 100644 --- a/libbutl/filesystem.ixx +++ b/libbutl/filesystem.ixx @@ -186,4 +186,131 @@ namespace butl { return dir_iterator (); } + + // path_pattern_iterator + // + inline path_pattern_iterator:: + path_pattern_iterator (std::string::const_iterator begin, + std::string::const_iterator end) + : i_ (begin), + e_ (end) + { + next (); // If i_ == e_ we will end up with the end iterator. + } + + inline path_pattern_iterator:: + path_pattern_iterator (const std::string& s) + : path_pattern_iterator (s.begin (), s.end ()) + { + } + + inline bool + operator== (const path_pattern_iterator& x, const path_pattern_iterator& y) + { + return x.t_.has_value () == y.t_.has_value () && + (!x.t_ || (x.i_ == y.i_ && x.e_ == y.e_)); + } + + inline bool + operator!= (const path_pattern_iterator& x, const path_pattern_iterator& y) + { + return !(x == y); + } + + inline path_pattern_iterator + begin (const path_pattern_iterator& i) + { + return i; + } + + inline path_pattern_iterator + end (const path_pattern_iterator&) + { + return path_pattern_iterator (); + } + + // patterns + // + inline char + get_literal (const path_pattern_term& t) + { + assert (t.literal ()); + return *t.begin; + } + + inline bool + path_pattern (const std::string& s) + { + for (const path_pattern_term& t: path_pattern_iterator (s)) + { + if (!t.literal ()) + return true; + } + + return false; + } + + // Return true for a pattern containing the specified number of the + // consecutive star wildcards. + // + inline bool + path_pattern_recursive (const std::string& s, size_t sn) + { + std::size_t n (0); + for (const path_pattern_term& t: path_pattern_iterator (s)) + { + if (t.star ()) + { + if (++n == sn) + return true; + } + else + n = 0; + } + + return false; + } + + inline bool + path_pattern_recursive (const std::string& s) + { + return path_pattern_recursive (s, 2); + } + + inline bool + path_pattern_self_matching (const std::string& s) + { + return path_pattern_recursive (s, 3); + } + + inline bool + path_pattern (const path& p) + { + for (auto i (p.begin ()); i != p.end (); ++i) + { + if (path_pattern (*i)) + return true; + } + + return false; + } + + inline size_t + path_pattern_recursive (const path& p) + { + std::size_t r (0); + for (auto i (p.begin ()); i != p.end (); ++i) + { + if (path_pattern_recursive (*i)) + ++r; + } + + return r; + } + + inline bool + path_pattern_self_matching (const path& p) + { + return !p.empty () && path_pattern_self_matching (*p.begin ()); + } } diff --git a/libbutl/filesystem.mxx b/libbutl/filesystem.mxx index e028975..24922a1 100644 --- a/libbutl/filesystem.mxx +++ b/libbutl/filesystem.mxx @@ -20,11 +20,14 @@ #ifndef _MSC_VER # include <sys/types.h> // mode_t #else - typedef int mode_t; + using mode_t = int; #endif +#include <cassert> + #ifndef __cpp_lib_modules_ts -#include <cstddef> // ptrdiff_t +#include <string> +#include <cstddef> // ptrdiff_t, size_t #include <cstdint> // uint16_t, etc #include <utility> // move(), pair #include <iterator> @@ -42,11 +45,13 @@ import std.core; #endif import butl.path; +import butl.optional; import butl.timestamp; import butl.utility; #else #include <libbutl/path.mxx> +#include <libbutl/optional.mxx> #include <libbutl/timestamp.mxx> #include <libbutl/utility.mxx> @@ -602,7 +607,7 @@ LIBBUTL_MODEXPORT namespace butl class LIBBUTL_SYMEXPORT dir_entry { public: - typedef butl::path path_type; + using path_type = butl::path; // Symlink target type in case of the symlink, ltype() otherwise. // @@ -641,11 +646,11 @@ LIBBUTL_MODEXPORT namespace butl class LIBBUTL_SYMEXPORT dir_iterator { public: - typedef dir_entry value_type; - typedef const dir_entry* pointer; - typedef const dir_entry& reference; - typedef std::ptrdiff_t difference_type; - typedef std::input_iterator_tag iterator_category; + using value_type = dir_entry; + using pointer = const dir_entry*; + using reference = const dir_entry&; + using difference_type = std::ptrdiff_t; + using iterator_category = std::input_iterator_tag; ~dir_iterator (); dir_iterator () = default; @@ -714,10 +719,19 @@ LIBBUTL_MODEXPORT namespace butl // Wildcard pattern match and search (aka glob). // - // Currently the following wildcard characters are supported: + // The wildcard pattern contains the literal characters that match + // themselves and the wildcard characters that match a single or multiple + // characters. Currently the following wildcards are supported: + // + // * - match any number of characters (including zero) + // ? - match any single character + // [...] - match a character with a "bracket expression"; currently we only + // support literal characters and ranges (no character/equivalence + // classes, etc; see Pattern Matching Notation section of the Shell + // Command Language POSIX specification for details) // - // * - match any number of characters (including zero) - // ? - match any single character + // Note also that currently we don't support the special characters + // backslash-escaping (as mandated by POSIX). // Path match/search flags. // @@ -869,6 +883,134 @@ LIBBUTL_MODEXPORT namespace butl bool interm)>&, const dir_path& start = dir_path (), path_match_flags = path_match_flags::none); + + // Return true if a name contains the wildcard characters. + // + bool + path_pattern (const std::string&); + + // Return true if a name contains the ** wildcard sequences. + // + bool + path_pattern_recursive (const std::string&); + + // Return true if a name contains the *** wildcard sequences. + // + bool + path_pattern_self_matching (const std::string&); + + // Return true if a path contains the pattern components. + // + bool + path_pattern (const path&); + + // Return the number of recursive pattern components. + // + // Knowing the number of such components allows us to make some assumptions + // regarding the search result. For example, if it is zero or one, then the + // result contains no duplicates. + // + // Also note that the result can be used as bool. + // + size_t + path_pattern_recursive (const path&); + + // Return true if the path is not empty and its first component is a self- + // matching pattern. + // + bool + path_pattern_self_matching (const path&); + + // Iteration over pattern terminals. + // + enum class path_pattern_term_type + { + literal, // Literal character. + question, // Question mark wildcard. + star, // Star wildcard. + bracket // Bracket expression wildcard. + }; + + class path_pattern_term + { + public: + path_pattern_term_type type; + std::string::const_iterator begin; + std::string::const_iterator end; + + std::size_t + size () const {return end - begin;} + + // Predicates. + // + bool literal () const {return type == path_pattern_term_type::literal;} + bool question () const {return type == path_pattern_term_type::question;} + bool star () const {return type == path_pattern_term_type::star;} + bool bracket () const {return type == path_pattern_term_type::bracket;} + }; + + // Return the literal terminal character. + // + char + get_literal (const path_pattern_term&); + + // Match a character against the bracket expression terminal. + // + LIBBUTL_SYMEXPORT bool + match_bracket (char, const path_pattern_term&); + + class LIBBUTL_SYMEXPORT path_pattern_iterator + { + public: + using value_type = path_pattern_term; + using pointer = const path_pattern_term*; + using reference = const path_pattern_term&; + using difference_type = std::ptrdiff_t; + using iterator_category = std::input_iterator_tag; + + explicit + path_pattern_iterator (const std::string&); + + path_pattern_iterator (std::string::const_iterator begin, + std::string::const_iterator end); + + path_pattern_iterator () = default; // Create the end iterator. + + path_pattern_iterator& operator++ () {assert (t_); next (); return *this;} + + reference operator* () const {assert (t_); return *t_;} + pointer operator-> () const {assert (t_); return &*t_;} + + friend bool + operator== (const path_pattern_iterator&, const path_pattern_iterator&); + + friend bool + operator!= (const path_pattern_iterator&, const path_pattern_iterator&); + + private: + void + next (); + + private: + // nullopt denotes the end iterator. + // + // Note that the default-constructed i_ and e_ iterators (having singular + // values) may not represent the end iterator as are not comparable for + // equality. That's why we use an absent term to represent such an + // iterator. + // + optional<path_pattern_term> t_; + + std::string::const_iterator i_; + std::string::const_iterator e_; + }; + + // Range-based for loop support. + // + // for (const path_pattern_term& t: path_pattern_iterator (pattern)) ... + // + path_pattern_iterator begin (const path_pattern_iterator&); + path_pattern_iterator end (const path_pattern_iterator&); } #include <libbutl/filesystem.ixx> diff --git a/tests/wildcard/testscript b/tests/wildcard/testscript index a7ddb1a..4b88427 100644 --- a/tests/wildcard/testscript +++ b/tests/wildcard/testscript @@ -75,17 +75,76 @@ } } + : bracket + : + { + : ordinary-char + : + { + $* a[bc]d abd : first + $* a[0-9b]d abd : after-range + $* a[bc]d acd : last + $* a[]bc]d a]d : closing-bracket + $* a[-bc]d a-d : first-dash + $* a[bc-]d a-d : last-dash + $* a[*]d a*d : star + $* a[?]d a?d : question + $* a[[]d a[d : open-bracket + $* a[xy]d abd == 1 : not-match + + : not-expr + : + { + $* a[b a[b : not-closed + $* a[!b a[!b : not-closed-inverse + $* a[]b a[]b : empty + $* a[!] a[!] : empty-inverse + } + } + + : range + : + { + $* a[0-8]d a0d : min + $* a[0-8]d a8d : max + $* a[0-8]d a5d : mid + $* a[0-8]d a9d == 1 : out + $* a[a0-8]d a1d : after-char + $* a[x0-9y]d abd == 1 : not-match + } + + : inverse + : + { + $* a[!xy]d abd : match + $* a[!ab]d abd == 1 : not-match + } + } + + : mixed + : + : Test patterns combining backtracking with the bracket expressions. + : + { + $* [0-9]a*b 9axb : bracket-star + $* a*b[0-9] axyb0 : star-bracket + $* a*b[0-9]x*y ab1xzy : star-bracket-star + $* a*[0-9]x*y[a-z] ax2xyb : star-bracket-star-bracket + } + : case-sensitivity : : Test that matching is case-insensitive on Windows and sensitive otherwise. : if ($cxx.target.class != 'windows') { - $* F*O/ foo/ == 1 + $* F*O/ foo/ == 1 + $* f[A-Z]o/ foo/ == 1 } else { - $* F*O/ foo/ + $* F*O/ foo/ + $* f[A-Z]o/ foo/ } } @@ -161,6 +220,13 @@ baz EOO + : recursive-with-brackets + : + $* **[!xy][rz] ../foo >>/EOO + bar/bar + baz + EOO + : self-recursive : { |