Rust: Tracking issue for (DoubleEnded)?Iterator::rfind

[clarfonthey]

PR: #39399

Unanswered: should this method be part of DoubleEndedIterator or Iterator?

Pros:

• Avoids cluttering Iterator docs
• Avoids extra constraint in where clause
• Puts method where it is actually enabled

Cons:

• Inconsistency if other methods (rev, rposition) aren't moved to DEI
• Breaking change if other methods are moved to DEI
• Fragments iterator docs; no longer just in Iterator
• Requires typing DoubleEndedIterator::rfind if passed into a function instead of Iterator::find

Noting the above, should Iterator::rev and Iterator::rposition be moved to DEI as well?

[andrewjstone]

Personally, I'd like to see rfind in Iterator since rposition is already in there. I'm not a huge fan of the splitting of operations required by DEI. However, I agree that if rfind is stabilized in DEI, rev and rposition should probably be moved. Of course this will cause breaking changes as mentioned here.

[bluss]

It was already not the case that all iterator functionality sits in Iterator, and I don't think it should be like that.

I just noticed the docs for rfind says "from the right" and should probably say "from the back", the r should be about reverse (like rev) and not left vs right (instead front vs back or forward vs reverse).

[bluss]

Something that seems like a small drawback of having the method in Iterator is that it makes the mechanics of specialization tricky. (Maybe this is easy to solve). I want to add a specialization to the implementation of Iterator for &mut I where I: Sized.

The code that exists in rust today:

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, I: Iterator + ?Sized> Iterator for &'a mut I {
    type Item = I::Item;
    fn next(&mut self) -> Option<I::Item> { (**self).next() }
    fn size_hint(&self) -> (usize, Option<usize>) { (**self).size_hint() }
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        (**self).nth(n)
    }
}

Let's add specialization for I: Sized so that we forward iterator methods better, when we can. I hope the first one serves as a good example.

This compiles fine:

impl<'a, I: Iterator> Iterator for &'a mut I {
    fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
        where P: FnMut(&Self::Item) -> bool,
    {
        (**self).find(predicate)
    }
}

And this, rfind can be specialized the same way:

impl<'a, I: DoubleEndedIterator> DoubleEndedIterator for &'a mut I {
    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
        where P: FnMut(&Self::Item) -> bool,
    {
        (**self).rfind(predicate)
    }
}

Having trouble with this one -- rposition:

Try 1, as part of the Iterator specialization block above:

    fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
        P: FnMut(Self::Item) -> bool,
        Self: ExactSizeIterator + DoubleEndedIterator
    {
        (**self).rposition(predicate)
    }

First error (the rest are the same kind):

error[E0277]: the trait bound `I: iter::traits::ExactSizeIterator` is not satisfied
    --> src/libcore/iter/iterator.rs:2301:18
     |
2301 |         (**self).rposition(predicate)
     |                  ^^^^^^^^^ the trait `iter::traits::ExactSizeIterator` is not implemented for `I`
     |
     = help: consider adding a `where I: iter::traits::ExactSizeIterator` bound

Try 2, we can use a separate specialization block:

impl<'a, I: Iterator> Iterator for &'a mut I
    where I: ExactSizeIterator + DoubleEndedIterator
{
    fn rposition<P>(&mut self, predicate: P) -> Option<usize> where
        P: FnMut(Self::Item) -> bool,
        Self: ExactSizeIterator + DoubleEndedIterator
    {
        (**self).rposition(predicate)
    }
}

Error (We can't use the suggestion because "impl has stricter requirements than trait"):

error[E0277]: the trait bound `P: ops::function::FnMut<(<I as iter::iterator::Iterator>::Item,)>` is not satisfied
    --> src/libcore/iter/iterator.rs:2315:18
     |
2315 |         (**self).rposition(predicate)
     |                  ^^^^^^^^^ the trait `ops::function::FnMut<(<I as iter::iterator::Iterator>::Item,)>` is not implemented for `P`
     |
     = help: consider adding a `where P: ops::function::FnMut<(<I as iter::iterator::Iterator>::Item,)>` bound

[scottmcm]

With rfold (https://github.com/rust-lang/rust/issues/44705#issuecomment-373929270) and try_rfold (https://github.com/rust-lang/rust/issues/45594#issuecomment-373932187) in P-FCP on DoubleEndedIterator, can we take that as a decision that rmethods go on DEI, and thus this is also ready for P-FCP? Especially given bluss's arguments above.

[SimonSapin]

Breaking changes to stable std APIs are of course non-starters, so rev and rposition will stay where they are. If that turns out to be a mistake, it’s one we’ll have to live with.

I agree that DoubleEndedIterator is where rfind belong, too bad for the inconsistency. Let’s leave it there, change “from the right” to “from the back”, and stabilize.

@rfcbot fcp merge

[rfcbot]

Team member @SimonSapin has proposed to merge this. The next step is review by the rest of the tagged teams:

• [x] @Kimundi
• [x] @SimonSapin
• [x] @alexcrichton
• [ ] @aturon
• [x] @dtolnay
• [x] @sfackler
• [x] @withoutboats

No concerns currently listed.

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

[rfcbot]

The final comment period is now complete.