core/iter/adapters/
fuse.rs

1use crate::intrinsics;
2use crate::iter::adapters::SourceIter;
3use crate::iter::adapters::zip::try_get_unchecked;
4use crate::iter::{
5    FusedIterator, TrustedFused, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce,
6};
7use crate::ops::Try;
8
9/// An iterator that yields `None` forever after the underlying iterator
10/// yields `None` once.
11///
12/// This `struct` is created by [`Iterator::fuse`]. See its documentation
13/// for more.
14#[derive(Clone, Debug)]
15#[must_use = "iterators are lazy and do nothing unless consumed"]
16#[stable(feature = "rust1", since = "1.0.0")]
17pub struct Fuse<I> {
18    // NOTE: for `I: FusedIterator`, we never bother setting `None`, but
19    // we still have to be prepared for that state due to variance.
20    // See rust-lang/rust#85863
21    iter: Option<I>,
22}
23impl<I> Fuse<I> {
24    pub(in crate::iter) fn new(iter: I) -> Fuse<I> {
25        Fuse { iter: Some(iter) }
26    }
27
28    pub(crate) fn into_inner(self) -> Option<I> {
29        self.iter
30    }
31}
32
33#[stable(feature = "fused", since = "1.26.0")]
34impl<I> FusedIterator for Fuse<I> where I: Iterator {}
35
36#[unstable(issue = "none", feature = "trusted_fused")]
37unsafe impl<I> TrustedFused for Fuse<I> where I: TrustedFused {}
38
39// Any specialized implementation here is made internal
40// to avoid exposing default fns outside this trait.
41#[stable(feature = "rust1", since = "1.0.0")]
42impl<I> Iterator for Fuse<I>
43where
44    I: Iterator,
45{
46    type Item = <I as Iterator>::Item;
47
48    #[inline]
49    fn next(&mut self) -> Option<Self::Item> {
50        FuseImpl::next(self)
51    }
52
53    #[inline]
54    fn nth(&mut self, n: usize) -> Option<I::Item> {
55        FuseImpl::nth(self, n)
56    }
57
58    #[inline]
59    fn last(self) -> Option<Self::Item> {
60        match self.iter {
61            Some(iter) => iter.last(),
62            None => None,
63        }
64    }
65
66    #[inline]
67    fn count(self) -> usize {
68        match self.iter {
69            Some(iter) => iter.count(),
70            None => 0,
71        }
72    }
73
74    #[inline]
75    fn size_hint(&self) -> (usize, Option<usize>) {
76        match self.iter {
77            Some(ref iter) => iter.size_hint(),
78            None => (0, Some(0)),
79        }
80    }
81
82    #[inline]
83    fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
84    where
85        Self: Sized,
86        Fold: FnMut(Acc, Self::Item) -> R,
87        R: Try<Output = Acc>,
88    {
89        FuseImpl::try_fold(self, acc, fold)
90    }
91
92    #[inline]
93    fn fold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc
94    where
95        Fold: FnMut(Acc, Self::Item) -> Acc,
96    {
97        if let Some(iter) = self.iter {
98            acc = iter.fold(acc, fold);
99        }
100        acc
101    }
102
103    #[inline]
104    fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
105    where
106        P: FnMut(&Self::Item) -> bool,
107    {
108        FuseImpl::find(self, predicate)
109    }
110
111    #[inline]
112    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
113    where
114        Self: TrustedRandomAccessNoCoerce,
115    {
116        match self.iter {
117            // SAFETY: the caller must uphold the contract for
118            // `Iterator::__iterator_get_unchecked`.
119            Some(ref mut iter) => unsafe { try_get_unchecked(iter, idx) },
120            // SAFETY: the caller asserts there is an item at `i`, so we're not exhausted.
121            None => unsafe { intrinsics::unreachable() },
122        }
123    }
124}
125
126#[stable(feature = "rust1", since = "1.0.0")]
127impl<I> DoubleEndedIterator for Fuse<I>
128where
129    I: DoubleEndedIterator,
130{
131    #[inline]
132    fn next_back(&mut self) -> Option<<I as Iterator>::Item> {
133        FuseImpl::next_back(self)
134    }
135
136    #[inline]
137    fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item> {
138        FuseImpl::nth_back(self, n)
139    }
140
141    #[inline]
142    fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
143    where
144        Self: Sized,
145        Fold: FnMut(Acc, Self::Item) -> R,
146        R: Try<Output = Acc>,
147    {
148        FuseImpl::try_rfold(self, acc, fold)
149    }
150
151    #[inline]
152    fn rfold<Acc, Fold>(self, mut acc: Acc, fold: Fold) -> Acc
153    where
154        Fold: FnMut(Acc, Self::Item) -> Acc,
155    {
156        if let Some(iter) = self.iter {
157            acc = iter.rfold(acc, fold);
158        }
159        acc
160    }
161
162    #[inline]
163    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
164    where
165        P: FnMut(&Self::Item) -> bool,
166    {
167        FuseImpl::rfind(self, predicate)
168    }
169}
170
171#[stable(feature = "rust1", since = "1.0.0")]
172impl<I> ExactSizeIterator for Fuse<I>
173where
174    I: ExactSizeIterator,
175{
176    fn len(&self) -> usize {
177        match self.iter {
178            Some(ref iter) => iter.len(),
179            None => 0,
180        }
181    }
182
183    fn is_empty(&self) -> bool {
184        match self.iter {
185            Some(ref iter) => iter.is_empty(),
186            None => true,
187        }
188    }
189}
190
191#[stable(feature = "default_iters", since = "1.70.0")]
192impl<I: Default> Default for Fuse<I> {
193    /// Creates a `Fuse` iterator from the default value of `I`.
194    ///
195    /// ```
196    /// # use core::slice;
197    /// # use std::iter::Fuse;
198    /// let iter: Fuse<slice::Iter<'_, u8>> = Default::default();
199    /// assert_eq!(iter.len(), 0);
200    /// ```
201    fn default() -> Self {
202        Fuse { iter: Default::default() }
203    }
204}
205
206#[unstable(feature = "trusted_len", issue = "37572")]
207// SAFETY: `TrustedLen` requires that an accurate length is reported via `size_hint()`. As `Fuse`
208// is just forwarding this to the wrapped iterator `I` this property is preserved and it is safe to
209// implement `TrustedLen` here.
210unsafe impl<I> TrustedLen for Fuse<I> where I: TrustedLen {}
211
212#[doc(hidden)]
213#[unstable(feature = "trusted_random_access", issue = "none")]
214// SAFETY: `TrustedRandomAccess` requires that `size_hint()` must be exact and cheap to call, and
215// `Iterator::__iterator_get_unchecked()` must be implemented accordingly.
216//
217// This is safe to implement as `Fuse` is just forwarding these to the wrapped iterator `I`, which
218// preserves these properties.
219unsafe impl<I> TrustedRandomAccess for Fuse<I> where I: TrustedRandomAccess {}
220
221#[doc(hidden)]
222#[unstable(feature = "trusted_random_access", issue = "none")]
223unsafe impl<I> TrustedRandomAccessNoCoerce for Fuse<I>
224where
225    I: TrustedRandomAccessNoCoerce,
226{
227    const MAY_HAVE_SIDE_EFFECT: bool = I::MAY_HAVE_SIDE_EFFECT;
228}
229
230/// Fuse specialization trait
231///
232/// We only need to worry about `&mut self` methods, which
233/// may exhaust the iterator without consuming it.
234#[doc(hidden)]
235trait FuseImpl<I> {
236    type Item;
237
238    // Functions specific to any normal Iterators
239    fn next(&mut self) -> Option<Self::Item>;
240    fn nth(&mut self, n: usize) -> Option<Self::Item>;
241    fn try_fold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
242    where
243        Self: Sized,
244        Fold: FnMut(Acc, Self::Item) -> R,
245        R: Try<Output = Acc>;
246    fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
247    where
248        P: FnMut(&Self::Item) -> bool;
249
250    // Functions specific to DoubleEndedIterators
251    fn next_back(&mut self) -> Option<Self::Item>
252    where
253        I: DoubleEndedIterator;
254    fn nth_back(&mut self, n: usize) -> Option<Self::Item>
255    where
256        I: DoubleEndedIterator;
257    fn try_rfold<Acc, Fold, R>(&mut self, acc: Acc, fold: Fold) -> R
258    where
259        Self: Sized,
260        Fold: FnMut(Acc, Self::Item) -> R,
261        R: Try<Output = Acc>,
262        I: DoubleEndedIterator;
263    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
264    where
265        P: FnMut(&Self::Item) -> bool,
266        I: DoubleEndedIterator;
267}
268
269/// General `Fuse` impl which sets `iter = None` when exhausted.
270#[doc(hidden)]
271impl<I> FuseImpl<I> for Fuse<I>
272where
273    I: Iterator,
274{
275    type Item = <I as Iterator>::Item;
276
277    #[inline]
278    default fn next(&mut self) -> Option<<I as Iterator>::Item> {
279        and_then_or_clear(&mut self.iter, Iterator::next)
280    }
281
282    #[inline]
283    default fn nth(&mut self, n: usize) -> Option<I::Item> {
284        and_then_or_clear(&mut self.iter, |iter| iter.nth(n))
285    }
286
287    #[inline]
288    default fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
289    where
290        Self: Sized,
291        Fold: FnMut(Acc, Self::Item) -> R,
292        R: Try<Output = Acc>,
293    {
294        if let Some(ref mut iter) = self.iter {
295            acc = iter.try_fold(acc, fold)?;
296            self.iter = None;
297        }
298        try { acc }
299    }
300
301    #[inline]
302    default fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
303    where
304        P: FnMut(&Self::Item) -> bool,
305    {
306        and_then_or_clear(&mut self.iter, |iter| iter.find(predicate))
307    }
308
309    #[inline]
310    default fn next_back(&mut self) -> Option<<I as Iterator>::Item>
311    where
312        I: DoubleEndedIterator,
313    {
314        and_then_or_clear(&mut self.iter, |iter| iter.next_back())
315    }
316
317    #[inline]
318    default fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item>
319    where
320        I: DoubleEndedIterator,
321    {
322        and_then_or_clear(&mut self.iter, |iter| iter.nth_back(n))
323    }
324
325    #[inline]
326    default fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
327    where
328        Self: Sized,
329        Fold: FnMut(Acc, Self::Item) -> R,
330        R: Try<Output = Acc>,
331        I: DoubleEndedIterator,
332    {
333        if let Some(ref mut iter) = self.iter {
334            acc = iter.try_rfold(acc, fold)?;
335            self.iter = None;
336        }
337        try { acc }
338    }
339
340    #[inline]
341    default fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
342    where
343        P: FnMut(&Self::Item) -> bool,
344        I: DoubleEndedIterator,
345    {
346        and_then_or_clear(&mut self.iter, |iter| iter.rfind(predicate))
347    }
348}
349
350/// Specialized `Fuse` impl which doesn't bother clearing `iter` when exhausted.
351/// However, we must still be prepared for the possibility that it was already cleared!
352#[doc(hidden)]
353impl<I> FuseImpl<I> for Fuse<I>
354where
355    I: FusedIterator,
356{
357    #[inline]
358    fn next(&mut self) -> Option<<I as Iterator>::Item> {
359        self.iter.as_mut()?.next()
360    }
361
362    #[inline]
363    fn nth(&mut self, n: usize) -> Option<I::Item> {
364        self.iter.as_mut()?.nth(n)
365    }
366
367    #[inline]
368    fn try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
369    where
370        Self: Sized,
371        Fold: FnMut(Acc, Self::Item) -> R,
372        R: Try<Output = Acc>,
373    {
374        if let Some(ref mut iter) = self.iter {
375            acc = iter.try_fold(acc, fold)?;
376        }
377        try { acc }
378    }
379
380    #[inline]
381    fn find<P>(&mut self, predicate: P) -> Option<Self::Item>
382    where
383        P: FnMut(&Self::Item) -> bool,
384    {
385        self.iter.as_mut()?.find(predicate)
386    }
387
388    #[inline]
389    fn next_back(&mut self) -> Option<<I as Iterator>::Item>
390    where
391        I: DoubleEndedIterator,
392    {
393        self.iter.as_mut()?.next_back()
394    }
395
396    #[inline]
397    fn nth_back(&mut self, n: usize) -> Option<<I as Iterator>::Item>
398    where
399        I: DoubleEndedIterator,
400    {
401        self.iter.as_mut()?.nth_back(n)
402    }
403
404    #[inline]
405    fn try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, fold: Fold) -> R
406    where
407        Self: Sized,
408        Fold: FnMut(Acc, Self::Item) -> R,
409        R: Try<Output = Acc>,
410        I: DoubleEndedIterator,
411    {
412        if let Some(ref mut iter) = self.iter {
413            acc = iter.try_rfold(acc, fold)?;
414        }
415        try { acc }
416    }
417
418    #[inline]
419    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
420    where
421        P: FnMut(&Self::Item) -> bool,
422        I: DoubleEndedIterator,
423    {
424        self.iter.as_mut()?.rfind(predicate)
425    }
426}
427
428// This is used by Flatten's SourceIter impl
429#[unstable(issue = "none", feature = "inplace_iteration")]
430unsafe impl<I> SourceIter for Fuse<I>
431where
432    I: SourceIter + TrustedFused,
433{
434    type Source = I::Source;
435
436    #[inline]
437    unsafe fn as_inner(&mut self) -> &mut I::Source {
438        // SAFETY: unsafe function forwarding to unsafe function with the same requirements.
439        // TrustedFused guarantees that we'll never encounter a case where `self.iter` would
440        // be set to None.
441        unsafe { SourceIter::as_inner(self.iter.as_mut().unwrap_unchecked()) }
442    }
443}
444
445#[inline]
446fn and_then_or_clear<T, U>(opt: &mut Option<T>, f: impl FnOnce(&mut T) -> Option<U>) -> Option<U> {
447    let x = f(opt.as_mut()?);
448    if x.is_none() {
449        *opt = None;
450    }
451    x
452}