aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--butl/filesystem53
-rw-r--r--butl/filesystem.cxx369
-rw-r--r--butl/path2
-rw-r--r--tests/buildfile3
-rw-r--r--tests/wildcard/buildfile7
-rw-r--r--tests/wildcard/driver.cxx105
-rw-r--r--tests/wildcard/testscript378
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);
+ }
}
diff --git a/butl/path b/butl/path
index a81848b..19e3d42 100644
--- a/butl/path
+++ b/butl/path
@@ -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
+ }
+ }
+ }
+ }
+}