8000 Redesign the std::iter::Step trait, tweak related iterator impls for ranges by SimonSapin · Pull Request #43127 · rust-lang/rust · GitHub
[go: up one dir, main page]
Skip to content

Redesign the std::iter::Step trait, tweak related iterator impls for ranges #43127

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.

Sign up for GitHub

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

Closed
wants to merge 11 commits into from
Closed

Redesign the std::iter::Step trait, tweak related iterator impls for ranges #43127

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
11 commits
Select commit Hold shift + click to select a range
d103522
Check integer overflow/underflow in Range* iterators
SimonSapin Jul 6, 2017
3e8a762
Don’t reset RangeInclusive to 1...0 after last iteration.
SimonSapin Jul 6, 2017
5334226
Rename Step::{add,sub}_usize to Step::forward and Step::backward
SimonSapin Jul 7, 2017
32d963e
Rewrite mixed-width mixed-signedness integer arithmetic in Step impls
SimonSapin Jul 7, 2017
9d4dc29
Add tests for Step trait methods
SimonSapin Jul 7, 2017
c0b4440
Implement TrustedLen for ranges of all integer types
SimonSapin Jul 8, 2017
b270e7f
Tighter size_hint lower bound for ranges larger than usize
SimonSapin Jul 8, 2017
287ce4c
Remove ExactSizeIterator impls for RangeInclusive<{i16,u16}>
SimonSapin Jul 8, 2017
eed9884
Add a comment on the `start > end` check in RangeInclusive::size_hint
SimonSapin Jul 8, 2017
0a62269
Make tidy happy
SimonSapin Jul 9, 2017
0ac7fca
Implement TrustedLen for ranges of all T: Step, make Step an unsafe t…
SimonSapin Jul 9, 2017
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Implement TrustedLen for ranges of all T: Step, make Step an unsafe t… 
…rait.
  • Loading branch information
@SimonSapin
SimonSapin committed Jul 24, 2017
commit 0ac7fca8341f132d228d95fa7c6d5e9c07763969
73 changes: 30 additions & 43 deletions src/libcore/iter/range.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -17,15 +17,23 @@ use super::{FusedIterator, TrustedLen};

/// Objects that have a notion of *successor* and *predecessor*
/// for the purpose of range iterators.
///
/// This trait is `unsafe` because implementations of the `unsafe` trait `TrustedLen`
/// depend on its implementations being correct.
#[unstable(feature = "step_trait",
reason = "recently redesigned",
issue = "42168")]
pub trait Step: Clone + PartialOrd + Sized {
pub unsafe trait Step: Clone + PartialOrd + Sized {
/// Returns the number of *successor* steps needed to get from `start` to `end`.
///
/// Returns `None` if that number would overflow `usize`
/// (or is infinite, if `end` would never be reached).
/// Returns `Some(0)` if `start` comes after (is greater than) or equals `end`.
///
/// This must hold for any `a`, `b`, and `n`:
///
/// * `steps_between(&a, &b) == Some(0)` if and only if `a >= b`.
/// * `steps_between(&a, &b) == Some(n)` if and only if `a.forward(n) == Some(b)`
/// * `steps_between(&a, &b) == Some(n)` if and only if `b.backward(n) == Some(a)`
fn steps_between(start: &Self, end: &Self) -> Option<usize>;

/// Returns the value that would be obtained by taking the *successor* of `self`,
Expand All @@ -35,6 +43,10 @@ pub trait Step: Clone + PartialOrd + Sized {
///
/// Note: `step_count == 1` is a common case,
/// used for example in `Iterator::next` for ranges.
Copy link
Member
@scottmcm scottmcm Jul 15, 2017 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Would it be worth a fn forward_one(&self) -> Option<Self> { self.forward(1) } (or call it successor, perhaps, like the comment here does) so the common case is overridable if needed? I suppose it's always addable later if needed.

///
/// This must hold for any `a`, `n`, and `m` where `n + m` doesn’t overflow:
///
/// * `a.forward(n).and_then(|x| x.forward(m)) == a.forward(n + m)`
fn forward(&self, step_count: usize) -> Option<Self>;

/// Returns the value that would be obtained by taking the *predecessor* of `self`,
Expand All @@ -44,6 +56,10 @@ pub trait Step: Clone + PartialOrd + Sized {
///
/// Note: `step_count == 1` is a common case,
/// used for example in `Iterator::next_back` for ranges.
///
/// This must hold for any `a`, `n`, and `m` where `n + m` doesn’t overflow:
///
/// * `a.backward(n).and_then(|x| x.backward(m)) == a.backward(n + m)`
fn backward(&self, step_count: usize) -> Option<Self>;
}

Expand All @@ -58,11 +74,9 @@ macro_rules! step_integer_impls {
#[unstable(feature = "step_trait",
reason = "recently redesigned",
issue = "42168")]
impl Step for $narrower_unsigned {
unsafe impl Step for $narrower_unsigned {
#[inline]
fn steps_between(start: &Self, end: &Self) -> Option<usize> {
// NOTE: the safety of `unsafe impl TrustedLen` depends on
// this being correct!
if *start < *end {
// This relies on $narrower_unsigned <= usize
Some((*end - *start) as usize)
Expand Down Expand Up @@ -91,11 +105,9 @@ macro_rules! step_integer_impls {
#[unstable(feature = "step_trait",
reason = "recently redesigned",
issue = "42168")]
impl Step for $narrower_signed {
unsafe impl Step for $narrower_signed {
#[inline]
fn steps_between(start: &Self, end: &Self) -> Option<usize> {
// NOTE: the safety of `unsafe impl TrustedLen` depends on
// this being correct!
if *start < *end {
// This relies on $narrower_signed <= usize
//
Expand Down Expand Up @@ -157,11 +169,9 @@ macro_rules! step_integer_impls {
#[unstable(feature = "step_trait",
reason = "recently redesigned",
issue = "42168")]
impl Step for $wider_unsigned {
unsafe impl Step for $wider_unsigned {
#[inline]
fn steps_between(start: &Self, end: &Self) -> Option<usize> {
// NOTE: the safety of `unsafe impl TrustedLen` depends on
// this being correct!
if *start < *end {
usize::try_from(*end - *start).ok()
} else {
Expand All @@ -183,11 +193,9 @@ macro_rules! step_integer_impls {
#[unstable(feature = "step_trait",
reason = "recently redesigned",
issue = "42168")]
impl Step for $wider_signed {
unsafe impl Step for $wider_signed {
#[inline]
fn steps_between(start: &Self, end: &Self) -> Option<usize> {
// NOTE: the safety of `unsafe impl TrustedLen` depends on
// this being correct!
if *start < *end {
match end.checked_sub(*start) {
Some(diff) => usize::try_from(diff).ok(),
Expand Down Expand Up @@ -248,22 +256,6 @@ macro_rules! range_incl_exact_iter_impl {
)*)
}

macro_rules! range_trusted_len_impl {
($($t:ty)*) => ($(
#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl TrustedLen for ops::Range<$t> { }
)*)
}

macro_rules! range_incl_trusted_len_impl {
($($t:ty)*) => ($(
#[unstable(feature = "inclusive_range",
reason = "recently added, follows RFC",
issue = "28237")]
unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
)*)
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Step> Iterator for ops::Range<A> {
type Item = A;
Expand Down Expand Up @@ -335,19 +327,6 @@ range_incl_exact_iter_impl! {
i8
}

// These macros generate `TrustedLen` impls.
//
// They need to guarantee that .size_hint() is either exact, or that
// the upper bound is None when it does not fit the type limits.
range_trusted_len_impl! {
usize u8 u16 u32 u64 u128
isize i8 i16 i32 i64 i128
}
range_incl_trusted_len_impl! {
usize u8 u16 u32 u64 u128
isize i8 i16 i32 i64 i128
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Step> DoubleEndedIterator for ops::Range<A> {
#[inline]
Expand All @@ -362,6 +341,9 @@ impl<A: Step> DoubleEndedIterator for ops::Range<A> {
}
}

#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<T: Step> TrustedLen for ops::Range<T> {}

#[unstable(feature = "fused", issue = "35602")]
impl<A: Step> FusedIterator for ops::Range<A> {}

Expand Down Expand Up @@ -507,5 +489,10 @@ impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
}
}

#[unstable(feature = "inclusive_range",
reason = "recently added, follows RFC",
issue = "28237")]
unsafe impl<T: Step> TrustedLen for ops::RangeInclusive<T> { }

#[unstable(feature = "fused", issue = "35602")]
impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}
2 changes: 1 addition & 1 deletion src/test/run-pass/impl-trait/example-calendar.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -161,7 +161,7 @@ impl<'a, 'b> std::ops::Add<&'b NaiveDate> for &'a NaiveDate {
}
}

impl std::iter::Step for NaiveDate {
unsafe impl std::iter::Step for NaiveDate {
fn steps_between(_: &Self, _: &Self) -> Option<usize> {
unimplemented!()
}
Expand Down
0