ACP: Introduce something akin to reverse ancestor method/iterator for `std::path`

[asder8215]

Proposal

Problem statement

Currently, in std::path, there are multiple methods that produces an iterator for Path that lets you iterate through components of a path or parents of a path. For example, say I have this:

let path = Path::new("/foo/bar/text.txt");

If we use path.iter(), we get the following from iterating through Iter<'_>:

"/"
"foo"
"bar"
"text.txt"

If we use path.components(), we get the following result from iterating through an Components<'_> iterator:

RootDir
Normal("foo")
Normal("bar")
Normal("text.txt")

And if we use path.ancestors(), we get the following from iterating through a Ancestor<'_> iterator:

"/foo/bar/text.txt"
"/foo/bar"
"/foo"
"/"

The Ancestors<'_> iterator is very useful in many programs or functions that want to iteratively apply changes to the current path and its parent paths. However, we currently don't have an iterator in std::path that mirrors what the Ancestors<'_> iterator does in the opposite direction. That is, from let path = Path::new("/foo/bar/text.txt");, we should be able to iterate through an iterator that shows the following:

"/"
"/foo"
"/foo/bar"
"/foo/bar/text.txt"

And note: Ancestors<'_> only implements Iterator and FusedIterator (though if it implemented DoubleEndedIterator, I don't think it would produce the above results, and just strip from the beginning components, like "foo/bar/text.txt", "bar/text.txt", "text.txt", "").

Motivating examples or use cases

The motivation behind this ACP came from my time changing the implementation for std::fs::create_dir_all() a while back from a recursive version of creating the current directory and its parent components to an iterative version; this was to avoid a stack overflow issue that could occur on Windows with a deeply nested path of uncreated directories (see this issue).

In my iterative implementation of create_dir_all() (see here), I used the Ancestors<'_> iterator to find the first (parent) path to create before I can move in the forward direction to create the rest of the directories. How I went about creating the remaining directories was through using a counter (in traversing to the first path to create), Vec::with_capacity(counter), and extending the Vec with ancestors.take(counter). This allowed me to transform the Vec<&Path> into a reversed iterator, allowing me to create the remaining directories. However, doing this still costed me a O(N) space (similar to the recursive solution, just instead of stack it's on heap) when we could have went with an optimized O(1) (whilst keeping time complexity at O(N)) by reusing the path given to us.

The idea for this proposal was actually from @Mark-Simulacrum in reviewing my PR that commented on the allocation for Vec<&Path> being unfortunate as we lacked a "children"/reversed ancestor API, and he also gave his own sketch on what this API could look like.

All together, I think it would make std::path consistent to introduce a "children"/reversed ancestor API with how we have an ancestor API, and many people could possible have use for such an API.

Solution sketch

This is a solution sketch of the Children API I came up with (which differs from the one Mark proposed in my create_dir_all() PR).

#![feature(stmt_expr_attributes)] // for the cfg blocks I use here
#![feature(path_trailing_sep)] // for removing trailing '/' or '\\'
use std::{ffi::OsStr, path::{Path, Prefix}};

#[derive(Copy, Clone, Debug)] // consistent with traits that Ancestor<'a> derives
struct Children<'a> {
    path: &'a [u8],
    #[cfg(target_os = "windows")]
    prefix: Option<Prefix<'a>>, // we don't need this on non-windows OS
    end: usize, // the end index to show our forward path
}

// this is taken from std::path from Prefix::len
#[cfg(target_os = "windows")]
fn prefix_len(prefix: Prefix) -> usize {
    use self::Prefix::*;
    fn os_str_len(s: &OsStr) -> usize {
        s.as_encoded_bytes().len()
    }
    match prefix {
        Verbatim(x) => 4 + os_str_len(x),
        VerbatimUNC(x, y) => {
            8 + os_str_len(x) + if os_str_len(y) > 0 { 1 + os_str_len(y) } else { 0 }
        }
        VerbatimDisk(_) => 6,
        UNC(x, y) => 2 + os_str_len(x) + if os_str_len(y) > 0 { 1 + os_str_len(y) } else { 0 },
        DeviceNS(x) => 4 + os_str_len(x),
        Disk(_) => 2,
    }
}

// Note this may run on certain platforms like
// UEFI or Solid ASP3 (which uses '\\'), so instead of these functions
// we rely on is_sep_byte() that's already privately imported in
// std::path from std::sys::path
#[inline]
#[cfg(not(target_os = "windows"))]
fn is_sep_byte(b: u8) -> bool {
    b == b'/'
}
#[inline]
#[cfg(target_os = "windows")]
fn is_sep_byte(b: u8) -> bool {
    b == b'\\' || b == b'/'
}

impl<'a> Iterator for Children<'a> {
    type Item = &'a Path;

    fn next(&mut self) -> Option<Self::Item> {
        // we've reached the end of the iterator if our
        // end is >= path given to us
        if self.end >= self.path.len() {
            return None;
        }
        
        // if we have a prefix, we can just start iterating through bytes
        // after prefix len
        #[cfg(target_os = "windows")]
        if let Some(prefix) = self.prefix {
            self.end += prefix_len(prefix);
            self.prefix = None; // prefix consumed
        }
  
        let mut check_trailing_sep = false;
        // find the first separator byte that delimits the path
        while self.end < self.path.len() {
            if is_sep_byte(self.path[self.end]) {
                check_trailing_sep = true;
                self.end += 1;
                break; 
            }
            self.end += 1;
        }
        
        // if there are trailing sep bytes, then we continue until 
        // we don't see anymore sep bytes
        while check_trailing_sep {
            if self.end >= self.path.len() {
                break;
            } else if !is_sep_byte(self.path[self.end]) {
                break;
            }
            self.end += 1;
        }
        
        // SAFETY: A valid path must have been passed into our iterator
        // and our `OsStr` encode bytes with "an unspecified, platform-specific,
        // self-synchronizing superset of UTF-8", which means that we wouldn't
        // touch the middle of a code point if we delimit on ascii separators like '/' or '\\'
        // (which are 1 byte)
        // To shorten this code, we could use Path::from_u8_slice() as seen for .ancestors(), 
        // but that's a private function it seems...
        let sliced_path = unsafe { OsStr::from_encoded_bytes_unchecked(&self.path[0..self.end]) };
        // we trim the trailing sep (which note doesn't do anything to '/' path) to
        // have returned path be consistent with Ancestor iterator 
        Some(Path::new(sliced_path).trim_trailing_sep())
    }
}

impl Path {
// A mirror on how .ancestors() returns its Ancestor<'_> iterator
// but we could probably just reduce this into one function with
// cfg blocks on what to return for specific platforms?
#[cfg(target_os = "windows")]
fn children(&self, path: &Path) -> Children<'_> {
    Children { path: path.as_os_str().as_encoded_bytes(), prefix: parse_prefix(path), end: 0}
}
#[cfg(not(target_os = "windows"))]
fn children(&self) -> Children<'_> {
    Children { path: self.as_os_str().as_encoded_bytes(), end: 0}
}
}

This implementation of the children/reversed ancestor API uses a reference to the path (no extra allocation of path needed) and consumes the iterator in O(N) or O(# of components path has). You can try it out a version of it reimplementing the private functions into accessible functions here.

Alternatives

Alternatively:

• A reverse ancestor API could be handwritten, which I've shown in the solution sketch (or people could use heap allocated reversed iterator on a Vec approach that I've done for create_dir_all(), but that isn't optimal on space).

• We could also use Mark's Children API here:

use std::path::Components;
use std::ffi::OsStr;
use std::path::Path;

fn main() {
    let path = Path::new("/tmp/foo/bar.txt");
    let mut children = Children::new(path);
    
    // Desired sequence:
    // /tmp
    // /tmp/foo
    // /tmp/foo/bar.txt

    dbg!(children.collect::<Vec<_>>());
}

struct Children<'a> {
    original: &'a Path,
    iterated: Components<'a>,
    done: bool,
}

impl<'a> Children<'a> {
    fn new(path: &'a Path) -> Self {
        let mut iterated = path.components();
        iterated.next();
        Children { original: path, iterated, done: false }
    }
}

impl<'a> Iterator for Children<'a> {
    type Item = &'a Path;
    
    fn next(&mut self) -> Option<Self::Item> {
        if self.done {
            return None;
        }
    
        let orig = self.original.as_os_str().as_encoded_bytes();
        let remaining_suffix = self.iterated.as_path().as_os_str().as_encoded_bytes();
        if remaining_suffix.is_empty() {
            self.done = true;
        }
        self.iterated.next();
        
        let prefix = orig.strip_suffix(remaining_suffix).expect("path ends with own suffix");
    
        // SAFETY: TODO, but I think justified:
        // we only split on something `components()` would split on,
        // and it splits only on path separators (\\ or / depending on platform) which are UTF-8.
        // We could use https://doc.rust-lang.org/nightly/std/ffi/struct.OsStr.html#method.slice_encoded_bytes
        // to guarantee safety at the cost of a panic if we get it wrong.
        unsafe {
            Some(Path::new(OsStr::from_encoded_bytes_unchecked(prefix)))
        }
    }
}

The issue I think with this solution is that to walk through the Children<'_> iterator on each step you strip the remaining components/suffix from the original string in this part:

let prefix = orig.strip_suffix(remaining_suffix).expect("path ends with own suffix");

Walking through the full Children<'_> iterator here would be O(N^2) (or O(components^2))

• As mentioned in the discussion below, we could also change how Ancestors<'_> struct looks like from this:

#[derive(Copy, Clone, Debug)]
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "path_ancestors", since = "1.28.0")]
pub struct Ancestors<'a> {
    next: Option<&'a Path>,
}

#[stable(feature = "path_ancestors", since = "1.28.0")]
impl<'a> Iterator for Ancestors<'a> {
    type Item = &'a Path;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        let next = self.next;
        self.next = next.and_then(Path::parent);
        next
    }
}

#[stable(feature = "path_ancestors", since = "1.28.0")]
impl FusedIterator for Ancestors<'_> {}

To something like this:

#[derive(Copy, Clone, Debug)]
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "path_ancestors", since = "1.28.0")]
pub struct Ancestors<'a> {
    next: &'a [u8],
    front: usize,
    back: usize,
}

#[stable(feature = "path_ancestors", since = "1.28.0")]
impl<'a> Iterator for Ancestors<'a> {
    type Item = &'a Path;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        ... 
    }
}

impl<'a> DoubleEndedIterator for Ancestors<'a> {
    type Item = &'a Path;
    
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        ... 
    }
}

#[stable(feature = "path_ancestors", since = "1.28.0")]
impl FusedIterator for Ancestors<'_> {}

This would preserve how Ancestors<'_> iterator works currently (actually optimizing it a bit from using Path::parent, which uses Components<'_> .next_back() and .as_path() to get the parent path), and only introduce the DoubleEndedIterator trait to it, which shouldn't be a breaking change. We can take advantage of a front and back index strategy to get a slice of the path properly on .next()/.next_back(). This option would prevent us from creating a whole new iterator for the forward path when they can use a reversible iterator on Ancestors<'_>.

Links and related work

• Implement create_dir_all() to operate iteratively instead of recursively rust#148196

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[programmerjake]

"/"
"/foo"
"/foo/bar"
"/foo/bar/text.txt"

in the parenthetical below you're confusing reversing the order items are produced by the iterator with the order of components of the path; if Ancestors implemented DoubleEndedIterator, then path.ancestors().rev() would produce exactly what you wanted above and wouldn't strip components from the beginning.

And note: Ancestors<'_> only implements Iterator and FusedIterator (though if it implemented DoubleEndedIterator, I don't think it would produce the above results, and just strip from the beginning components, like "foo/bar/text.txt", "bar/text.txt", "text.txt", "").

Any properly implemented iterator should produce the exact same results with rev() as with collect::<Vec<_>>().into_iter().rev()

[asder8215]

in the parenthetical below you're confusing reversing the order items are produced by the iterator with the order of components of the path; if Ancestors implemented DoubleEndedIterator, then path.ancestors().rev() would produce exactly what you wanted above and wouldn't strip components from the beginning.

You're exactly right; I think this should be the expected behavior for path.ancestors().rev(). It's what felt intuitive to me when I was doing the create_dir_all() PR.

I think the reason why I mentioned about "foo/bar/text.txt", "bar/text.txt", "text.txt", "" was because underneath the hood for Ancestor<'_>, which uses Path::parent, it uses the Components<'_>, calls next_back() (which strips away the last component), and then converts remaining components as a Path. I thought if we were still to rely on Components<'_> for Ancestor<'_>, a reversed iterator version would use Components<'_> next() method (stripping away beginning components) and then convert the remaining components as a Path.

That does leave the option of seeing if we can redesign or expand Ancestor<'_> to support implementing the DoubleEndedIterator trait. I would imagine if we capture collect::<Vec<_>>().into_iter(), then reversing the iterator in the middle of traversing it would look something like this:

let path = Path::new("/foo/bar/text.txt");
let mut ancestors = path.ancestors();

println!("{:?}", ancestors.next()) // prints "/foo/bar/text.txt"
println!("{:?}", ancestors.next()) // prints "/foo/bar"

let mut rev_ancestor = ancestors.rev(); // consumes ancestors var as well

println!("{:?}", ancestors.next()) // prints "/"
println!("{:?}", ancestors.next()) // prints "/foo"

^ I think we can capture this behavior if we made the Ancestors<'_> struct look like this:

pub struct Ancestors<'a> {
path: &'a [u8],
front: usize, // init to 0
back: usize // init to len of the path
}

we would still get a u8 slice of the path using path[..front] or path[..back], but .next() would decrement back, and .next_back() would increment front. Our iterator would return None if it sees that back < front (in next()) or that front > back (in next_back()).

Separately, doing this does make me think having a Cursor API for Path might be nice to be able to go back and forward without having this consuming behavior.

[ChrisDenton]

I think this could potentially also be added as a method to Components. There's already an as_path which is really a "remaining path" function. We could add a method to return the preceding path. However that does mean changing the implementation to keep the full path so we can return the part up to the current position. I don't know if that would have any consequences for existing code.

[asder8215]

I think this could potentially also be added as a method to Components. There's already an as_path which is really a "remaining path" function. We could add a method to return the preceding path. However that does mean changing the implementation to keep the full path so we can return the part up to the current position. I don't know if that would have any consequences for existing code.

We could try changing Components<'_> internal implementation from:

#[derive(Clone)]
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Components<'a> {
    // The path left to parse components from
    path: &'a [u8],

    // The prefix as it was originally parsed, if any
    prefix: Option<Prefix<'a>>,

    // true if path *physically* has a root separator; for most Windows
    // prefixes, it may have a "logical" root separator for the purposes of
    // normalization, e.g., \\server\share == \\server\share\.
    has_physical_root: bool,

    // The iterator is double-ended, and these two states keep track of what has
    // been produced from either end
    front: State,
    back: State,
}

to

#[derive(Clone)]
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Components<'a> {
    // The path left to parse components from
    path: &'a [u8],

    // The prefix as it was originally parsed, if any
    prefix: Option<Prefix<'a>>,

    // true if path *physically* has a root separator; for most Windows
    // prefixes, it may have a "logical" root separator for the purposes of
    // normalization, e.g., \\server\share == \\server\share\.
    has_physical_root: bool,

    // The iterator is double-ended, and these two states keep track of what has
    // been produced from either end
    front: usize,
    back: usize,
}

I think we can change what front and back is to using a usize value to slice the appropriate portion of the path instead of how it currently trims the path with trim_left() and trim_right(). We can use helper functions (or modify existing ones) to return a Option<Component<'a>> so that it keeps the current behavior of its iterator to show if a component of a path is a CurrDir, RootDir, Normal(...), etc..; it's possible to do this because if we're using .next(), we already have the start position of the component from what's initially stored in front, and when we reach a separator byte like / or \\ that's our end position, so we'd just parse path[front_original..front] (and vice versa for .next_back() doing path[back..back_original]). as_path() would just use path[front..back]. I'm not too certain how you imagine a preceding method should look like, but if the desired behavior is to show the full path all the way to the back component, you could do path[0..back] as well as introduce a front version of this method that shows the full path all the way to the front component through path[0..front]; this would likely need a couple methods that tells the user what the current front/back component is without consuming it.

Honestly, this does make it sound like you can do what Ancestor<'_> API (and reverse version of it) through Components<'_> itself.

[the8472]

I don't think you need to change Components, its as_path is always a subslice of the Path from which it was derived, so you can do offset-based subslicing if you have the original path. Ancestors holds a Path, not Components, so it should be able to to do that.

[the8472]

We discussed this in today's libs-api meeting, we're happy to have this and would like to see it implemented as DoubleEndedIterator for Ancestors if possible, so this can just be called ancestors().rev().

The suggested children() method did not gain consensus, so we'd like to leave this out. If it can't be implemented in Ancestors we might reconsider, though possibly with a different name.

Please open a tracking issue and then close this issue.