range.rs

use crate::convert::TryFrom;
use crate::mem;
use crate::ops::{self, Add, Sub, Try};
use crate::usize;

use super::{FusedIterator, TrustedLen};

/// Objects that can be stepped over in both directions.
///
/// The `steps_between` function provides a way to efficiently compare
/// two `Step` objects.
#[unstable(feature = "step_trait",
           reason = "likely to be replaced by finer-grained traits",
           issue = "42168")]
pub trait Step: Clone + PartialOrd + Sized {
    /// Returns the number of steps between two step objects. The count is
    /// inclusive of `start` and exclusive of `end`.
    ///
    /// Returns `None` if it is not possible to calculate `steps_between`
    /// without overflow.
    fn steps_between(start: &Self, end: &Self) -> Option<usize>;

    /// Replaces this step with `1`, returning itself.
    fn replace_one(&mut self) -> Self;

    /// Replaces this step with `0`, returning itself.
    fn replace_zero(&mut self) -> Self;

    /// Adds one to this step, returning the result.
    fn add_one(&self) -> Self;

    /// Subtracts one to this step, returning the result.
    fn sub_one(&self) -> Self;

    /// Adds a `usize`, returning `None` on overflow.
    fn add_usize(&self, n: usize) -> Option<Self>;

    /// Subtracts a `usize`, returning `None` on underflow.
    fn sub_usize(&self, n: usize) -> Option<Self> {
        // this default implementation makes the addition of `sub_usize` a non-breaking change
        let _ = n;
        unimplemented!()
    }
}

// These are still macro-generated because the integer literals resolve to different types.
macro_rules! step_identical_methods {
    () => {
        #[inline]
        fn replace_one(&mut self) -> Self {
            mem::replace(self, 1)
        }

        #[inline]
        fn replace_zero(&mut self) -> Self {
            mem::replace(self, 0)
        }

        #[inline]
        fn add_one(&self) -> Self {
            Add::add(*self, 1)
        }

        #[inline]
        fn sub_one(&self) -> Self {
            Sub::sub(*self, 1)
        }
    }
}

macro_rules! step_impl_unsigned {
    ($($t:ty)*) => ($(
        #[unstable(feature = "step_trait",
                   reason = "likely to be replaced by finer-grained traits",
                   issue = "42168")]
        impl Step for $t {
            #[inline]
            fn steps_between(start: &$t, end: &$t) -> Option<usize> {
                if *start < *end {
                    usize::try_from(*end - *start).ok()
                } else {
                    Some(0)
                }
            }

            #[inline]
            #[allow(unreachable_patterns)]
            fn add_usize(&self, n: usize) -> Option<Self> {
                match <$t>::try_from(n) {
                    Ok(n_as_t) => self.checked_add(n_as_t),
                    Err(_) => None,
                }
            }

            #[inline]
            #[allow(unreachable_patterns)]
            fn sub_usize(&self, n: usize) -> Option<Self> {
                match <$t>::try_from(n) {
                    Ok(n_as_t) => self.checked_sub(n_as_t),
                    Err(_) => None,
                }
            }

            step_identical_methods!();
        }
    )*)
}
macro_rules! step_impl_signed {
    ($( [$t:ty : $unsigned:ty] )*) => ($(
        #[unstable(feature = "step_trait",
                   reason = "likely to be replaced by finer-grained traits",
                   issue = "42168")]
        impl Step for $t {
            #[inline]
            fn steps_between(start: &$t, end: &$t) -> Option<usize> {
                if *start < *end {
                    // Use .wrapping_sub and cast to unsigned to compute the
                    // difference that may not fit inside the range of $t.
                    usize::try_from(end.wrapping_sub(*start) as $unsigned).ok()
                } else {
                    Some(0)
                }
            }

            #[inline]
            #[allow(unreachable_patterns)]
            fn add_usize(&self, n: usize) -> Option<Self> {
                match <$unsigned>::try_from(n) {
                    Ok(n_as_unsigned) => {
                        // Wrapping in unsigned space handles cases like
                        // `-120_i8.add_usize(200) == Some(80_i8)`,
                        // even though 200_usize is out of range for i8.
                        let wrapped = (*self as $unsigned).wrapping_add(n_as_unsigned) as $t;
                        if wrapped >= *self {
                            Some(wrapped)
                        } else {
                            None  // Addition overflowed
                        }
                    }
                    Err(_) => None,
                }
            }

            #[inline]
            #[allow(unreachable_patterns)]
            fn sub_usize(&self, n: usize) -> Option<Self> {
                match <$unsigned>::try_from(n) {
                    Ok(n_as_unsigned) => {
                        // Wrapping in unsigned space handles cases like
                        // `80_i8.sub_usize(200) == Some(-120_i8)`,
                        // even though 200_usize is out of range for i8.
                        let wrapped = (*self as $unsigned).wrapping_sub(n_as_unsigned) as $t;
                        if wrapped <= *self {
                            Some(wrapped)
                        } else {
                            None  // Subtraction underflowed
                        }
                    }
                    Err(_) => None,
                }
            }

            step_identical_methods!();
        }
    )*)
}

step_impl_unsigned!(usize u8 u16 u32 u64 u128);
step_impl_signed!([isize: usize] [i8: u8] [i16: u16]);
step_impl_signed!([i32: u32] [i64: u64] [i128: u128]);

macro_rules! range_exact_iter_impl {
    ($($t:ty)*) => ($(
        #[stable(feature = "rust1", since = "1.0.0")]
        impl ExactSizeIterator for ops::Range<$t> { }
    )*)
}

macro_rules! range_incl_exact_iter_impl {
    ($($t:ty)*) => ($(
        #[stable(feature = "inclusive_range", since = "1.26.0")]
        impl ExactSizeIterator for ops::RangeInclusive<$t> { }
    )*)
}

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 = "trusted_len", issue = "37572")]
        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;

    #[inline]
    fn next(&mut self) -> Option<A> {
        if self.start < self.end {
            // We check for overflow here, even though it can't actually
            // happen. Adding this check does however help llvm vectorize loops
            // for some ranges that don't get vectorized otherwise,
            // and this won't actually result in an extra check in an optimized build.
            if let Some(mut n) = self.start.add_usize(1) {
                mem::swap(&mut n, &mut self.start);
                Some(n)
            } else {
                None
            }
        } else {
            None
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        match Step::steps_between(&self.start, &self.end) {
            Some(hint) => (hint, Some(hint)),
            None => (usize::MAX, None)
        }
    }

    #[inline]
    fn nth(&mut self, n: usize) -> Option<A> {
        if let Some(plus_n) = self.start.add_usize(n) {
            if plus_n < self.end {
                self.start = plus_n.add_one();
                return Some(plus_n)
            }
        }

        self.start = self.end.clone();
        None
    }

    #[inline]
    fn last(mut self) -> Option<A> {
        self.next_back()
    }

    #[inline]
    fn min(mut self) -> Option<A> {
        self.next()
    }

    #[inline]
    fn max(mut self) -> Option<A> {
        self.next_back()
    }
}

// These macros generate `ExactSizeIterator` impls for various range types.
// Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded
// because they cannot guarantee having a length <= usize::MAX, which is
// required by ExactSizeIterator.
range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
range_incl_exact_iter_impl!(u8 u16 i8 i16);

// 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 isize u8 i8 u16 i16 u32 i32 u64 i64 u128 i128);
range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 u64 i64 u128 i128);

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Step> DoubleEndedIterator for ops::Range<A> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        if self.start < self.end {
            self.end = self.end.sub_one();
            Some(self.end.clone())
        } else {
            None
        }
    }

    #[inline]
    fn nth_back(&mut self, n: usize) -> Option<A> {
        if let Some(minus_n) = self.end.sub_usize(n) {
            if minus_n > self.start {
                self.end = minus_n.sub_one();
                return Some(self.end.clone())
            }
        }

        self.end = self.start.clone();
        None
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<A: Step> FusedIterator for ops::Range<A> {}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Step> Iterator for ops::RangeFrom<A> {
    type Item = A;

    #[inline]
    fn next(&mut self) -> Option<A> {
        let mut n = self.start.add_one();
        mem::swap(&mut n, &mut self.start);
        Some(n)
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        (usize::MAX, None)
    }

    #[inline]
    fn nth(&mut self, n: usize) -> Option<A> {
        let plus_n = self.start.add_usize(n).expect("overflow in RangeFrom::nth");
        self.start = plus_n.add_one();
        Some(plus_n)
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<A: Step> FusedIterator for ops::RangeFrom<A> {}

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

#[stable(feature = "inclusive_range", since = "1.26.0")]
impl<A: Step> Iterator for ops::RangeInclusive<A> {
    type Item = A;

    #[inline]
    fn next(&mut self) -> Option<A> {
        self.compute_is_empty();
        if self.is_empty.unwrap_or_default() {
            return None;
        }
        let is_iterating = self.start < self.end;
        self.is_empty = Some(!is_iterating);
        Some(if is_iterating {
            let n = self.start.add_one();
            mem::replace(&mut self.start, n)
        } else {
            self.start.clone()
        })
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        if self.is_empty() {
            return (0, Some(0));
        }

        match Step::steps_between(&self.start, &self.end) {
            Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
            None => (usize::MAX, None),
        }
    }

    #[inline]
    fn nth(&mut self, n: usize) -> Option<A> {
        self.compute_is_empty();
        if self.is_empty.unwrap_or_default() {
            return None;
        }

        if let Some(plus_n) = self.start.add_usize(n) {
            use crate::cmp::Ordering::*;

            match plus_n.partial_cmp(&self.end) {
                Some(Less) => {
                    self.is_empty = Some(false);
                    self.start = plus_n.add_one();
                    return Some(plus_n);
                }
                Some(Equal) => {
                    self.is_empty = Some(true);
                    return Some(plus_n);
                }
                _ => {}
            }
        }

        self.is_empty = Some(true);
        None
    }

    #[inline]
    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
    where
        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
    {
        self.compute_is_empty();

        if self.is_empty() {
            return Try::from_ok(init);
        }

        let mut accum = init;

        while self.start < self.end {
            let n = self.start.add_one();
            let n = mem::replace(&mut self.start, n);
            accum = f(accum, n)?;
        }

        self.is_empty = Some(true);

        if self.start == self.end {
            accum = f(accum, self.start.clone())?;
        }

        Try::from_ok(accum)
    }

    #[inline]
    fn last(mut self) -> Option<A> {
        self.next_back()
    }

    #[inline]
    fn min(mut self) -> Option<A> {
        self.next()
    }

    #[inline]
    fn max(mut self) -> Option<A> {
        self.next_back()
    }
}

#[stable(feature = "inclusive_range", since = "1.26.0")]
impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> {
    #[inline]
    fn next_back(&mut self) -> Option<A> {
        self.compute_is_empty();
        if self.is_empty.unwrap_or_default() {
            return None;
        }
        let is_iterating = self.start < self.end;
        self.is_empty = Some(!is_iterating);
        Some(if is_iterating {
            let n = self.end.sub_one();
            mem::replace(&mut self.end, n)
        } else {
            self.end.clone()
        })
    }

    #[inline]
    fn nth_back(&mut self, n: usize) -> Option<A> {
        self.compute_is_empty();
        if self.is_empty.unwrap_or_default() {
            return None;
        }

        if let Some(minus_n) = self.end.sub_usize(n) {
            use crate::cmp::Ordering::*;

            match minus_n.partial_cmp(&self.start) {
                Some(Greater) => {
                    self.is_empty = Some(false);
                    self.end = minus_n.sub_one();
                    return Some(minus_n);
                }
                Some(Equal) => {
                    self.is_empty = Some(true);
                    return Some(minus_n);
                }
                _ => {}
            }
        }

        self.is_empty = Some(true);
        None
    }

    #[inline]
    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
        Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
    {
        self.compute_is_empty();

        if self.is_empty() {
            return Try::from_ok(init);
        }

        let mut accum = init;

        while self.start < self.end {
            let n = self.end.sub_one();
            let n = mem::replace(&mut self.end, n);
            accum = f(accum, n)?;
        }

        self.is_empty = Some(true);

        if self.start == self.end {
            accum = f(accum, self.start.clone())?;
        }

        Try::from_ok(accum)
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<A: Step> FusedIterator for ops::RangeInclusive<A> {}