rust-dirstate: add helper to iterate ancestor paths

rust-dirstate: add helper to iterate ancestor paths

This is modeled after std::path::Path::ancestors().

find_dirs(b"") yields b"" because Mercurial's util.finddirs() works in that
way, and the test case for DirsMultiset expects such behavior.

--- a/rust/hg-core/src/utils/files.rs	Tue Jul 09 20:51:48 2019 -0400
+++ b/rust/hg-core/src/utils/files.rs	Sun Jun 30 18:32:43 2019 +0900
@@ -1,3 +1,4 @@
+use std::iter::FusedIterator;
 use std::path::Path;
 
 pub fn get_path_from_bytes(bytes: &[u8]) -> &Path {
@@ -17,3 +18,66 @@
 
     Path::new(os_str)
 }
+
+/// An iterator over repository path yielding itself and its ancestors.
+#[derive(Copy, Clone, Debug)]
+pub struct Ancestors<'a> {
+    next: Option<&'a [u8]>,
+}
+
+impl<'a> Iterator for Ancestors<'a> {
+    // if we had an HgPath type, this would yield &'a HgPath
+    type Item = &'a [u8];
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let next = self.next;
+        self.next = match self.next {
+            Some(s) if s.is_empty() => None,
+            Some(s) => {
+                let p = s.iter().rposition(|&c| c == b'/').unwrap_or(0);
+                Some(&s[..p])
+            }
+            None => None,
+        };
+        next
+    }
+}
+
+impl<'a> FusedIterator for Ancestors<'a> {}
+
+/// Returns an iterator yielding ancestor directories of the given repository
+/// path.
+///
+/// The path is separated by '/', and must not start with '/'.
+///
+/// The path itself isn't included unless it is b"" (meaning the root
+/// directory.)
+pub fn find_dirs<'a>(path: &'a [u8]) -> Ancestors<'a> {
+    let mut dirs = Ancestors { next: Some(path) };
+    if !path.is_empty() {
+        dirs.next(); // skip itself
+    }
+    dirs
+}
+
+#[cfg(test)]
+mod tests {
+    #[test]
+    fn find_dirs_some() {
+        let mut dirs = super::find_dirs(b"foo/bar/baz");
+        assert_eq!(dirs.next(), Some(b"foo/bar".as_ref()));
+        assert_eq!(dirs.next(), Some(b"foo".as_ref()));
+        assert_eq!(dirs.next(), Some(b"".as_ref()));
+        assert_eq!(dirs.next(), None);
+        assert_eq!(dirs.next(), None);
+    }
+
+    #[test]
+    fn find_dirs_empty() {
+        // looks weird, but mercurial.util.finddirs(b"") yields b""
+        let mut dirs = super::find_dirs(b"");
+        assert_eq!(dirs.next(), Some(b"".as_ref()));
+        assert_eq!(dirs.next(), None);
+        assert_eq!(dirs.next(), None);
+    }
+}