New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for (DoubleEnded)?Iterator::rfind #39480

Closed
clarcharr opened this Issue Feb 3, 2017 · 8 comments

Comments

Projects
None yet
8 participants
@clarcharr
Contributor

clarcharr commented Feb 3, 2017

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

This comment has been minimized.

Show comment
Hide comment
@andrewjstone

andrewjstone Jun 11, 2017

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.

andrewjstone commented Jun 11, 2017

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

This comment has been minimized.

Show comment
Hide comment
@bluss

bluss Jun 12, 2017

Contributor

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).

Contributor

bluss commented Jun 12, 2017

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

This comment has been minimized.

Show comment
Hide comment
@bluss

bluss Sep 19, 2017

Contributor

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
Contributor

bluss commented Sep 19, 2017

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

This comment has been minimized.

Show comment
Hide comment
@scottmcm

scottmcm Mar 17, 2018

Member

With rfold (#44705 (comment)) and try_rfold (#45594 (comment)) 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.

Member

scottmcm commented Mar 17, 2018

With rfold (#44705 (comment)) and try_rfold (#45594 (comment)) 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

This comment has been minimized.

Show comment
Hide comment
@SimonSapin

SimonSapin Mar 17, 2018

Contributor

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

Contributor

SimonSapin commented Mar 17, 2018

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

This comment has been minimized.

Show comment
Hide comment
@rfcbot

rfcbot Mar 17, 2018

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

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 commented Mar 17, 2018

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

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

This comment has been minimized.

Show comment
Hide comment
@rfcbot

rfcbot Mar 19, 2018

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

rfcbot commented Mar 19, 2018

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

@rfcbot

This comment has been minimized.

Show comment
Hide comment
@rfcbot

rfcbot Mar 29, 2018

The final comment period is now complete.

rfcbot commented Mar 29, 2018

The final comment period is now complete.

kennytm added a commit to kennytm/rust that referenced this issue Apr 4, 2018

Rollup merge of #49607 - cuviper:stable-iter-1.27, r=alexcrichton
Stabilize iterator methods in 1.27

- Closes #39480, feature  `iter_rfind`
  - `DoubleEndedIterator::rfind`
- Closes #44705, feature `iter_rfold`
  - `DoubleEndedIterator::rfold`
- Closes #45594, feature `iterator_try_fold`
  - `Iterator::try_fold`
  - `Iterator::try_for_each`
  - `DoubleEndedIterator::try_rfold`
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment