core/iter/adapters/
take.rs

1use crate::cmp;
2use crate::iter::adapters::SourceIter;
3use crate::iter::{FusedIterator, InPlaceIterable, TrustedFused, TrustedLen, TrustedRandomAccess};
4use crate::num::NonZero;
5use crate::ops::{ControlFlow, Try};
6
7/// An iterator that only iterates over the first `n` iterations of `iter`.
8///
9/// This `struct` is created by the [`take`] method on [`Iterator`]. See its
10/// documentation for more.
11///
12/// [`take`]: Iterator::take
13/// [`Iterator`]: trait.Iterator.html
14#[derive(Clone, Debug)]
15#[must_use = "iterators are lazy and do nothing unless consumed"]
16#[stable(feature = "rust1", since = "1.0.0")]
17#[ferrocene::prevalidated]
18pub struct Take<I> {
19    iter: I,
20    n: usize,
21}
22
23impl<I> Take<I> {
24    #[ferrocene::prevalidated]
25    pub(in crate::iter) fn new(iter: I, n: usize) -> Take<I> {
26        Take { iter, n }
27    }
28}
29
30#[stable(feature = "rust1", since = "1.0.0")]
31impl<I> Iterator for Take<I>
32where
33    I: Iterator,
34{
35    type Item = <I as Iterator>::Item;
36
37    #[inline]
38    #[ferrocene::prevalidated]
39    fn next(&mut self) -> Option<<I as Iterator>::Item> {
40        if self.n != 0 {
41            self.n -= 1;
42            self.iter.next()
43        } else {
44            None
45        }
46    }
47
48    #[inline]
49    #[ferrocene::prevalidated]
50    fn nth(&mut self, n: usize) -> Option<I::Item> {
51        if self.n > n {
52            self.n -= n + 1;
53            self.iter.nth(n)
54        } else {
55            if self.n > 0 {
56                self.iter.nth(self.n - 1);
57                self.n = 0;
58            }
59            None
60        }
61    }
62
63    #[inline]
64    #[ferrocene::prevalidated]
65    fn size_hint(&self) -> (usize, Option<usize>) {
66        if self.n == 0 {
67            return (0, Some(0));
68        }
69
70        let (lower, upper) = self.iter.size_hint();
71
72        let lower = cmp::min(lower, self.n);
73
74        let upper = match upper {
75            Some(x) if x < self.n => Some(x),
76            _ => Some(self.n),
77        };
78
79        (lower, upper)
80    }
81
82    #[inline]
83    #[ferrocene::prevalidated]
84    fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
85    where
86        Fold: FnMut(Acc, Self::Item) -> R,
87        R: Try<Output = Acc>,
88    {
89        #[ferrocene::prevalidated]
90        fn check<'a, T, Acc, R: Try<Output = Acc>>(
91            n: &'a mut usize,
92            mut fold: impl FnMut(Acc, T) -> R + 'a,
93        ) -> impl FnMut(Acc, T) -> ControlFlow<R, Acc> + 'a {
94            move |acc, x| {
95                *n -= 1;
96                let r = fold(acc, x);
97                if *n == 0 { ControlFlow::Break(r) } else { ControlFlow::from_try(r) }
98            }
99        }
100
101        if self.n == 0 {
102            try { init }
103        } else {
104            let n = &mut self.n;
105            self.iter.try_fold(init, check(n, fold)).into_try()
106        }
107    }
108
109    #[inline]
110    #[ferrocene::prevalidated]
111    fn fold<B, F>(self, init: B, f: F) -> B
112    where
113        Self: Sized,
114        F: FnMut(B, Self::Item) -> B,
115    {
116        Self::spec_fold(self, init, f)
117    }
118
119    #[inline]
120    #[ferrocene::prevalidated]
121    fn for_each<F: FnMut(Self::Item)>(self, f: F) {
122        Self::spec_for_each(self, f)
123    }
124
125    #[inline]
126    #[rustc_inherit_overflow_checks]
127    #[ferrocene::prevalidated]
128    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
129        let min = self.n.min(n);
130        let rem = match self.iter.advance_by(min) {
131            Ok(()) => 0,
132            Err(rem) => rem.get(),
133        };
134        let advanced = min - rem;
135        self.n -= advanced;
136        NonZero::new(n - advanced).map_or(Ok(()), Err)
137    }
138}
139
140#[unstable(issue = "none", feature = "inplace_iteration")]
141unsafe impl<I> SourceIter for Take<I>
142where
143    I: SourceIter,
144{
145    type Source = I::Source;
146
147    #[inline]
148    unsafe fn as_inner(&mut self) -> &mut I::Source {
149        // SAFETY: unsafe function forwarding to unsafe function with the same requirements
150        unsafe { SourceIter::as_inner(&mut self.iter) }
151    }
152}
153
154#[unstable(issue = "none", feature = "inplace_iteration")]
155unsafe impl<I: InPlaceIterable> InPlaceIterable for Take<I> {
156    const EXPAND_BY: Option<NonZero<usize>> = I::EXPAND_BY;
157    const MERGE_BY: Option<NonZero<usize>> = I::MERGE_BY;
158}
159
160#[stable(feature = "double_ended_take_iterator", since = "1.38.0")]
161impl<I> DoubleEndedIterator for Take<I>
162where
163    I: DoubleEndedIterator + ExactSizeIterator,
164{
165    #[inline]
166    fn next_back(&mut self) -> Option<Self::Item> {
167        if self.n == 0 {
168            None
169        } else {
170            let n = self.n;
171            self.n -= 1;
172            self.iter.nth_back(self.iter.len().saturating_sub(n))
173        }
174    }
175
176    #[inline]
177    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
178        let len = self.iter.len();
179        if self.n > n {
180            let m = len.saturating_sub(self.n) + n;
181            self.n -= n + 1;
182            self.iter.nth_back(m)
183        } else {
184            if len > 0 {
185                self.iter.nth_back(len - 1);
186            }
187            None
188        }
189    }
190
191    #[inline]
192    fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
193    where
194        Self: Sized,
195        Fold: FnMut(Acc, Self::Item) -> R,
196        R: Try<Output = Acc>,
197    {
198        if self.n == 0 {
199            try { init }
200        } else {
201            let len = self.iter.len();
202            if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
203                try { init }
204            } else {
205                self.iter.try_rfold(init, fold)
206            }
207        }
208    }
209
210    #[inline]
211    fn rfold<Acc, Fold>(mut self, init: Acc, fold: Fold) -> Acc
212    where
213        Self: Sized,
214        Fold: FnMut(Acc, Self::Item) -> Acc,
215    {
216        if self.n == 0 {
217            init
218        } else {
219            let len = self.iter.len();
220            if len > self.n && self.iter.nth_back(len - self.n - 1).is_none() {
221                init
222            } else {
223                self.iter.rfold(init, fold)
224            }
225        }
226    }
227
228    #[inline]
229    #[rustc_inherit_overflow_checks]
230    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
231        // The amount by which the inner iterator needs to be shortened for it to be
232        // at most as long as the take() amount.
233        let trim_inner = self.iter.len().saturating_sub(self.n);
234        // The amount we need to advance inner to fulfill the caller's request.
235        // take(), advance_by() and len() all can be at most usize, so we don't have to worry
236        // about having to advance more than usize::MAX here.
237        let advance_by = trim_inner.saturating_add(n);
238
239        let remainder = match self.iter.advance_back_by(advance_by) {
240            Ok(()) => 0,
241            Err(rem) => rem.get(),
242        };
243        let advanced_by_inner = advance_by - remainder;
244        let advanced_by = advanced_by_inner - trim_inner;
245        self.n -= advanced_by;
246        NonZero::new(n - advanced_by).map_or(Ok(()), Err)
247    }
248}
249
250#[stable(feature = "rust1", since = "1.0.0")]
251impl<I> ExactSizeIterator for Take<I> where I: ExactSizeIterator {}
252
253#[stable(feature = "fused", since = "1.26.0")]
254impl<I> FusedIterator for Take<I> where I: FusedIterator {}
255
256#[unstable(issue = "none", feature = "trusted_fused")]
257unsafe impl<I: TrustedFused> TrustedFused for Take<I> {}
258
259#[unstable(feature = "trusted_len", issue = "37572")]
260unsafe impl<I: TrustedLen> TrustedLen for Take<I> {}
261
262trait SpecTake: Iterator {
263    fn spec_fold<B, F>(self, init: B, f: F) -> B
264    where
265        Self: Sized,
266        F: FnMut(B, Self::Item) -> B;
267
268    fn spec_for_each<F: FnMut(Self::Item)>(self, f: F);
269}
270
271impl<I: Iterator> SpecTake for Take<I> {
272    #[inline]
273    #[ferrocene::prevalidated]
274    default fn spec_fold<B, F>(mut self, init: B, f: F) -> B
275    where
276        Self: Sized,
277        F: FnMut(B, Self::Item) -> B,
278    {
279        use crate::ops::NeverShortCircuit;
280        self.try_fold(init, NeverShortCircuit::wrap_mut_2(f)).0
281    }
282
283    #[inline]
284    #[ferrocene::prevalidated]
285    default fn spec_for_each<F: FnMut(Self::Item)>(mut self, f: F) {
286        // The default implementation would use a unit accumulator, so we can
287        // avoid a stateful closure by folding over the remaining number
288        // of items we wish to return instead.
289        #[ferrocene::prevalidated]
290        fn check<'a, Item>(
291            mut action: impl FnMut(Item) + 'a,
292        ) -> impl FnMut(usize, Item) -> Option<usize> + 'a {
293            move |more, x| {
294                action(x);
295                more.checked_sub(1)
296            }
297        }
298
299        let remaining = self.n;
300        if remaining > 0 {
301            self.iter.try_fold(remaining - 1, check(f));
302        }
303    }
304}
305
306impl<I: Iterator + TrustedRandomAccess> SpecTake for Take<I> {
307    #[inline]
308    fn spec_fold<B, F>(mut self, init: B, mut f: F) -> B
309    where
310        Self: Sized,
311        F: FnMut(B, Self::Item) -> B,
312    {
313        let mut acc = init;
314        let end = self.n.min(self.iter.size());
315        for i in 0..end {
316            // SAFETY: i < end <= self.iter.size() and we discard the iterator at the end
317            let val = unsafe { self.iter.__iterator_get_unchecked(i) };
318            acc = f(acc, val);
319        }
320        acc
321    }
322
323    #[inline]
324    fn spec_for_each<F: FnMut(Self::Item)>(mut self, mut f: F) {
325        let end = self.n.min(self.iter.size());
326        for i in 0..end {
327            // SAFETY: i < end <= self.iter.size() and we discard the iterator at the end
328            let val = unsafe { self.iter.__iterator_get_unchecked(i) };
329            f(val);
330        }
331    }
332}
333
334#[stable(feature = "exact_size_take_repeat", since = "1.82.0")]
335impl<T: Clone> DoubleEndedIterator for Take<crate::iter::Repeat<T>> {
336    #[inline]
337    fn next_back(&mut self) -> Option<Self::Item> {
338        self.next()
339    }
340
341    #[inline]
342    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
343        self.nth(n)
344    }
345
346    #[inline]
347    fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
348    where
349        Self: Sized,
350        Fold: FnMut(Acc, Self::Item) -> R,
351        R: Try<Output = Acc>,
352    {
353        self.try_fold(init, fold)
354    }
355
356    #[inline]
357    fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
358    where
359        Self: Sized,
360        Fold: FnMut(Acc, Self::Item) -> Acc,
361    {
362        self.fold(init, fold)
363    }
364
365    #[inline]
366    #[rustc_inherit_overflow_checks]
367    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
368        self.advance_by(n)
369    }
370}
371
372// Note: It may be tempting to impl DoubleEndedIterator for Take<RepeatWith>.
373// One must fight that temptation since such implementation wouldn’t be correct
374// because we have no way to return value of nth invocation of repeater followed
375// by n-1st without remembering all results.
376
377#[stable(feature = "exact_size_take_repeat", since = "1.82.0")]
378impl<T: Clone> ExactSizeIterator for Take<crate::iter::Repeat<T>> {
379    fn len(&self) -> usize {
380        self.n
381    }
382}
383
384#[stable(feature = "exact_size_take_repeat", since = "1.82.0")]
385impl<F: FnMut() -> A, A> ExactSizeIterator for Take<crate::iter::RepeatWith<F>> {
386    fn len(&self) -> usize {
387        self.n
388    }
389}
core/iter/adapters/take.rs

core/iter/adapters/
take.rs
