Add path_match() and path_search() overloads

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 ());