Separate `Components` iterator implementation into non-prefixed & prefixed versions

Proposal

Problem statement

For context on what the Components struct looks like, here it is:

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,
}

There's a lot of decisions made within Components to make it work both on Windows and non-Windows platform due to the presence of a Prefix component on Windows. Unfortunately, in trying to support Prefix components it causes performance issues on non-Windows platforms, particularly within Components::next_back/Path equality.

I think it would be highly preferable to separate implementation of Components (and anything that would have altering behavior due to differing Components implementation) into two different versions: a non-prefixed & a prefixed version (current implementation).

Motivating examples or use cases

I'll show you an excerpt of code from the current Components::next_back implementation:

impl<'a> DoubleEndedIterator for Components<'a> {
    fn next_back(&mut self) -> Option<Component<'a>> {
        while !self.finished() {
            match self.back {
                State::Body if self.path.len() > self.len_before_body() => {
                    let (size, comp) = self.parse_next_component_back();
                    self.path = &self.path[..self.path.len() - size];
                    if comp.is_some() {
                        return comp;
                    }
                }
                State::Body => {
                    self.back = State::StartDir;
                }
                ... // below is not relevant
        }
        None
    }
}

One of the bigger issues with Components::next_back is the first State::Body match, as it is the most frequent case it leans on. It checks if the current path's length is larger than length of the Prefix components + 1/2 if root directory and/or curr directory exists. That comparison is actually expensive if you look at it from the grand scheme of how often Path is used in things like cargo, filesystem operations, etc.. It degrades Path equality performance really badly if two Paths are not equal, as that leans on Components::next_back.

There are other performance issues unrelating to Prefix, such as using two different State enums to determine if we're done parsing the path when that could be centralized into one bool flag. You can see the impact of this within .finished:

#[inline]
    fn finished(&self) -> bool {
        self.front == State::Done || self.back == State::Done || self.front > self.back
    }

Where almost always we will be reaching the last boolean check because almost always we're not at a Done state or a state where self.front > self.back.

And then Components PartialEq implementation isn't full optimized either given how it doesn't find the first mismatching byte in a similar fashion to Components Ordering implementation before falling down to Components::next_back (using Iterator::eq will lead to parsing the component and then checking if the content between the two is the same, which causes redundant byte checking).

In a different re-implementation of Components I was working on here, which I've inserted that implementation locally in the rust repo and tested to make sure it passes test suite on non-Windows, I've made sure to avoid doing usize vs usize comparison in favor of using a bool flag to see if I need to work on the starting directory component. However, this implementation of mine leans on slicing away Prefix from the path field and putting it into its own prefix field as a Option<PrefixComponent<'a>> (current implementation preserves Prefix bytes in the path field on top of storing it in its own prefix field), and it's been a headache to consistently check if a Prefix exists or not (which, even though these are 1 byte checks from .is_some()/.is_none(), it does affect performance a bit for Path equality/ordering). For example, my implementation of Components::as_path does not support Windows because of the fact that my path field doesn't contain the Prefix component bytes and I have that stored away in a separate field (technically, I could utilize the raw pointer of Prefix and create a slice out of it with the length of Prefix + normalized path since I believe Prefix has the same raw pointer as the original Path, but it leads to unsafe code and I'm uncertain if the original path data will remain in that location even though we do have lifetime on Components for that).

If I got rid of Prefix entirely from my version of Components struct, it should improve the performance of Components, and consequently Path equality/comparison, entirely for non-Windows platform. The underlying implementation for my Components::next/Components::next_back does the same thing in subslicing the path field, but it normalizes away any in between or trailing redundant separators/current directory component bytes upfront instead of re-running through the while loop normalizing byte by byte going through the .finished 3 boolean check each.

Solution sketch

We could introduce these differing implementations of Components in library/std/src/sys/path as two different files, something like prefixed_paths.rs + nonprefixed_paths.rs (how we name & organize this could be left to discussion), and then re-export Components publicly within library/std/src/path.rs. Alternatively, we could something similar to what's done for ReadDir in std::fs, whereas we make Components a newtype wrapper around the different implementations of Components.

Other things that utilize Components underneath the hood that could have differing behaviors are the inner _push method that PathBuf::push uses and the Path::prefix (which is an internal method and not public), but these should be trivial to re-export. Everything else that relies on Components should have the same implementation still at least from my time working on the PR with redesigning Components implementation (which I realized subslicing is better than using a front and back index slicing).

One thing that might occur as a result of separating implementation of Components is that we may have unused code. For example, my Components implementation will result in Prefix::is_drive, Prefix::has_implicit_root being unused, but those methods are private to the Prefix enum, so it should be trivial to move those methods over to prefixed_paths.rs.

Alternatives

I mean, I'm sure it's possible for me to make a Components iterator that supports both Windows and non-Windows platform, but it sure isn't ideal to have non-Windows platforms bear the brunt of having a Prefix component.

Links and related work

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.

Start by reading the existing Components implementation under library/std/src/sys/path and its uses in library/std/src/path.rs, especially Components::next_back, equality, and PathBuf::push. Review the linked redesign and the libs-team feature lifecycle before proposing an implementation. Done would require team agreement on the split design and a tested implementation for prefixed and non-prefixed platforms.