core/iter/adapters/
skip.rs

1use crate::intrinsics::unlikely;
2#[cfg(not(feature = "ferrocene_subset"))]
3use crate::iter::adapters::SourceIter;
4#[cfg(not(feature = "ferrocene_subset"))]
5use crate::iter::adapters::zip::try_get_unchecked;
6#[cfg(not(feature = "ferrocene_subset"))]
7use crate::iter::{
8    FusedIterator, InPlaceIterable, TrustedFused, TrustedLen, TrustedRandomAccess,
9    TrustedRandomAccessNoCoerce,
10};
11use crate::num::NonZero;
12#[cfg(not(feature = "ferrocene_subset"))]
13use crate::ops::{ControlFlow, Try};
14
15// Ferrocene addition: imports for certified subset
16#[cfg(feature = "ferrocene_subset")]
17#[rustfmt::skip]
18use crate::ops::Try;
19
20/// An iterator that skips over `n` elements of `iter`.
21///
22/// This `struct` is created by the [`skip`] method on [`Iterator`]. See its
23/// documentation for more.
24///
25/// [`skip`]: Iterator::skip
26/// [`Iterator`]: trait.Iterator.html
27#[cfg_attr(not(feature = "ferrocene_subset"), derive(Clone, Debug))]
28#[must_use = "iterators are lazy and do nothing unless consumed"]
29#[stable(feature = "rust1", since = "1.0.0")]
30pub struct Skip<I> {
31    iter: I,
32    n: usize,
33}
34
35impl<I> Skip<I> {
36    pub(in crate::iter) fn new(iter: I, n: usize) -> Skip<I> {
37        Skip { iter, n }
38    }
39}
40
41#[stable(feature = "rust1", since = "1.0.0")]
42impl<I> Iterator for Skip<I>
43where
44    I: Iterator,
45{
46    type Item = <I as Iterator>::Item;
47
48    #[inline]
49    fn next(&mut self) -> Option<I::Item> {
50        if unlikely(self.n > 0) {
51            self.iter.nth(crate::mem::take(&mut self.n))
52        } else {
53            self.iter.next()
54        }
55    }
56
57    #[inline]
58    fn nth(&mut self, n: usize) -> Option<I::Item> {
59        if self.n > 0 {
60            let skip: usize = crate::mem::take(&mut self.n);
61            // Checked add to handle overflow case.
62            let n = match skip.checked_add(n) {
63                Some(nth) => nth,
64                None => {
65                    // In case of overflow, load skip value, before loading `n`.
66                    // Because the amount of elements to iterate is beyond `usize::MAX`, this
67                    // is split into two `nth` calls where the `skip` `nth` call is discarded.
68                    self.iter.nth(skip - 1)?;
69                    n
70                }
71            };
72            // Load nth element including skip.
73            self.iter.nth(n)
74        } else {
75            self.iter.nth(n)
76        }
77    }
78
79    #[inline]
80    fn count(mut self) -> usize {
81        if self.n > 0 {
82            // nth(n) skips n+1
83            if self.iter.nth(self.n - 1).is_none() {
84                return 0;
85            }
86        }
87        self.iter.count()
88    }
89
90    #[inline]
91    fn last(mut self) -> Option<I::Item> {
92        if self.n > 0 {
93            // nth(n) skips n+1
94            self.iter.nth(self.n - 1)?;
95        }
96        self.iter.last()
97    }
98
99    #[inline]
100    fn size_hint(&self) -> (usize, Option<usize>) {
101        let (lower, upper) = self.iter.size_hint();
102
103        let lower = lower.saturating_sub(self.n);
104        let upper = match upper {
105            Some(x) => Some(x.saturating_sub(self.n)),
106            None => None,
107        };
108
109        (lower, upper)
110    }
111
112    #[inline]
113    fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
114    where
115        Self: Sized,
116        Fold: FnMut(Acc, Self::Item) -> R,
117        R: Try<Output = Acc>,
118    {
119        let n = self.n;
120        self.n = 0;
121        if n > 0 {
122            // nth(n) skips n+1
123            if self.iter.nth(n - 1).is_none() {
124                return try { init };
125            }
126        }
127        self.iter.try_fold(init, fold)
128    }
129
130    #[inline]
131    fn fold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
132    where
133        Fold: FnMut(Acc, Self::Item) -> Acc,
134    {
135        if self.n > 0 {
136            // nth(n) skips n+1
137            if self.iter.nth(self.n - 1).is_none() {
138                return init;
139            }
140        }
141        self.iter.fold(init, fold)
142    }
143
144    #[inline]
145    #[rustc_inherit_overflow_checks]
146    fn advance_by(&mut self, mut n: usize) -> Result<(), NonZero<usize>> {
147        let skip_inner = self.n;
148        let skip_and_advance = skip_inner.saturating_add(n);
149
150        let remainder = match self.iter.advance_by(skip_and_advance) {
151            Ok(()) => 0,
152            Err(n) => n.get(),
153        };
154        let advanced_inner = skip_and_advance - remainder;
155        n -= advanced_inner.saturating_sub(skip_inner);
156        self.n = self.n.saturating_sub(advanced_inner);
157
158        // skip_and_advance may have saturated
159        if unlikely(remainder == 0 && n > 0) {
160            n = match self.iter.advance_by(n) {
161                Ok(()) => 0,
162                Err(n) => n.get(),
163            }
164        }
165
166        NonZero::new(n).map_or(Ok(()), Err)
167    }
168
169    #[doc(hidden)]
170    #[cfg(not(feature = "ferrocene_subset"))]
171    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
172    where
173        Self: TrustedRandomAccessNoCoerce,
174    {
175        // SAFETY: the caller must uphold the contract for
176        // `Iterator::__iterator_get_unchecked`.
177        //
178        // Dropping the skipped prefix when index 0 is passed is safe
179        // since
180        // * the caller passing index 0 means that the inner iterator has more items than `self.n`
181        // * TRA contract requires that get_unchecked will only be called once
182        //   (unless elements are copyable)
183        // * it does not conflict with in-place iteration since index 0 must be accessed
184        //   before something is written into the storage used by the prefix
185        unsafe {
186            if Self::MAY_HAVE_SIDE_EFFECT && idx == 0 {
187                for skipped_idx in 0..self.n {
188                    drop(try_get_unchecked(&mut self.iter, skipped_idx));
189                }
190            }
191
192            try_get_unchecked(&mut self.iter, idx + self.n)
193        }
194    }
195}
196
197#[stable(feature = "rust1", since = "1.0.0")]
198#[cfg(not(feature = "ferrocene_subset"))]
199impl<I> ExactSizeIterator for Skip<I> where I: ExactSizeIterator {}
200
201#[stable(feature = "double_ended_skip_iterator", since = "1.9.0")]
202#[cfg(not(feature = "ferrocene_subset"))]
203impl<I> DoubleEndedIterator for Skip<I>
204where
205    I: DoubleEndedIterator + ExactSizeIterator,
206{
207    fn next_back(&mut self) -> Option<Self::Item> {
208        if self.len() > 0 { self.iter.next_back() } else { None }
209    }
210
211    #[inline]
212    fn nth_back(&mut self, n: usize) -> Option<I::Item> {
213        let len = self.len();
214        if n < len {
215            self.iter.nth_back(n)
216        } else {
217            if len > 0 {
218                // consume the original iterator
219                self.iter.nth_back(len - 1);
220            }
221            None
222        }
223    }
224
225    fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
226    where
227        Self: Sized,
228        Fold: FnMut(Acc, Self::Item) -> R,
229        R: Try<Output = Acc>,
230    {
231        fn check<T, Acc, R: Try<Output = Acc>>(
232            mut n: usize,
233            mut fold: impl FnMut(Acc, T) -> R,
234        ) -> impl FnMut(Acc, T) -> ControlFlow<R, Acc> {
235            move |acc, x| {
236                n -= 1;
237                let r = fold(acc, x);
238                if n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) }
239            }
240        }
241
242        let n = self.len();
243        if n == 0 { try { init } } else { self.iter.try_rfold(init, check(n, fold)).into_try() }
244    }
245
246    impl_fold_via_try_fold! { rfold -> try_rfold }
247
248    #[inline]
249    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
250        let min = crate::cmp::min(self.len(), n);
251        let rem = self.iter.advance_back_by(min);
252        assert!(rem.is_ok(), "ExactSizeIterator contract violation");
253        NonZero::new(n - min).map_or(Ok(()), Err)
254    }
255}
256
257#[stable(feature = "fused", since = "1.26.0")]
258#[cfg(not(feature = "ferrocene_subset"))]
259impl<I> FusedIterator for Skip<I> where I: FusedIterator {}
260
261#[unstable(issue = "none", feature = "trusted_fused")]
262#[cfg(not(feature = "ferrocene_subset"))]
263unsafe impl<I: TrustedFused> TrustedFused for Skip<I> {}
264
265#[unstable(issue = "none", feature = "inplace_iteration")]
266#[cfg(not(feature = "ferrocene_subset"))]
267unsafe impl<I> SourceIter for Skip<I>
268where
269    I: SourceIter,
270{
271    type Source = I::Source;
272
273    #[inline]
274    unsafe fn as_inner(&mut self) -> &mut I::Source {
275        // SAFETY: unsafe function forwarding to unsafe function with the same requirements
276        unsafe { SourceIter::as_inner(&mut self.iter) }
277    }
278}
279
280#[unstable(issue = "none", feature = "inplace_iteration")]
281#[cfg(not(feature = "ferrocene_subset"))]
282unsafe impl<I: InPlaceIterable> InPlaceIterable for Skip<I> {
283    const EXPAND_BY: Option<NonZero<usize>> = I::EXPAND_BY;
284    const MERGE_BY: Option<NonZero<usize>> = I::MERGE_BY;
285}
286
287#[doc(hidden)]
288#[unstable(feature = "trusted_random_access", issue = "none")]
289#[cfg(not(feature = "ferrocene_subset"))]
290unsafe impl<I> TrustedRandomAccess for Skip<I> where I: TrustedRandomAccess {}
291
292#[doc(hidden)]
293#[unstable(feature = "trusted_random_access", issue = "none")]
294#[cfg(not(feature = "ferrocene_subset"))]
295unsafe impl<I> TrustedRandomAccessNoCoerce for Skip<I>
296where
297    I: TrustedRandomAccessNoCoerce,
298{
299    const MAY_HAVE_SIDE_EFFECT: bool = I::MAY_HAVE_SIDE_EFFECT;
300}
301
302// SAFETY: This adapter is shortening. TrustedLen requires the upper bound to be calculated correctly.
303// These requirements can only be satisfied when the upper bound of the inner iterator's upper
304// bound is never `None`. I: TrustedRandomAccess happens to provide this guarantee while
305// I: TrustedLen would not.
306#[unstable(feature = "trusted_len", issue = "37572")]
307#[cfg(not(feature = "ferrocene_subset"))]
308unsafe impl<I> TrustedLen for Skip<I> where I: Iterator + TrustedRandomAccess {}
core/iter/adapters/skip.rs

core/iter/adapters/
skip.rs
