1use crate::iter::adapters::SourceIter;
2use crate::iter::{
3 Cloned, Copied, Filter, FilterMap, Fuse, FusedIterator, InPlaceIterable, Map, TrustedFused,
4 TrustedLen,
5};
6use crate::iter::{Once, OnceWith};
7use crate::num::NonZeroUsize;
8use crate::ops::{ControlFlow, Try};
9use crate::result;
10use crate::{array, fmt, option};
11
12/// An iterator that maps each element to an iterator, and yields the elements
13/// of the produced iterators.
14///
15/// This `struct` is created by [`Iterator::flat_map`]. See its documentation
16/// for more.
17#[must_use = "iterators are lazy and do nothing unless consumed"]
18#[stable(feature = "rust1", since = "1.0.0")]
19pub struct FlatMap<I, U: IntoIterator, F> {
20 inner: FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>,
21}
22
23impl<I: Iterator, U: IntoIterator, F: FnMut(I::Item) -> U> FlatMap<I, U, F> {
24 pub(in crate::iter) fn new(iter: I, f: F) -> FlatMap<I, U, F> {
25 FlatMap { inner: FlattenCompat::new(iter:iter.map(f)) }
26 }
27
28 pub(crate) fn into_parts(self) -> (Option<U::IntoIter>, Option<I>, Option<U::IntoIter>) {
29 (
30 self.inner.frontiter,
31 self.inner.iter.into_inner().map(Map::into_inner),
32 self.inner.backiter,
33 )
34 }
35}
36
37#[stable(feature = "rust1", since = "1.0.0")]
38impl<I: Clone, U, F: Clone> Clone for FlatMap<I, U, F>
39where
40 U: Clone + IntoIterator<IntoIter: Clone>,
41{
42 fn clone(&self) -> Self {
43 FlatMap { inner: self.inner.clone() }
44 }
45}
46
47#[stable(feature = "core_impl_debug", since = "1.9.0")]
48impl<I: fmt::Debug, U, F> fmt::Debug for FlatMap<I, U, F>
49where
50 U: IntoIterator<IntoIter: fmt::Debug>,
51{
52 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53 f.debug_struct("FlatMap").field(name:"inner", &self.inner).finish()
54 }
55}
56
57#[stable(feature = "rust1", since = "1.0.0")]
58impl<I: Iterator, U: IntoIterator, F> Iterator for FlatMap<I, U, F>
59where
60 F: FnMut(I::Item) -> U,
61{
62 type Item = U::Item;
63
64 #[inline]
65 fn next(&mut self) -> Option<U::Item> {
66 self.inner.next()
67 }
68
69 #[inline]
70 fn size_hint(&self) -> (usize, Option<usize>) {
71 self.inner.size_hint()
72 }
73
74 #[inline]
75 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
76 where
77 Self: Sized,
78 Fold: FnMut(Acc, Self::Item) -> R,
79 R: Try<Output = Acc>,
80 {
81 self.inner.try_fold(init, fold)
82 }
83
84 #[inline]
85 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
86 where
87 Fold: FnMut(Acc, Self::Item) -> Acc,
88 {
89 self.inner.fold(init, fold)
90 }
91
92 #[inline]
93 fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
94 self.inner.advance_by(n)
95 }
96
97 #[inline]
98 fn count(self) -> usize {
99 self.inner.count()
100 }
101
102 #[inline]
103 fn last(self) -> Option<Self::Item> {
104 self.inner.last()
105 }
106}
107
108#[stable(feature = "rust1", since = "1.0.0")]
109impl<I: DoubleEndedIterator, U, F> DoubleEndedIterator for FlatMap<I, U, F>
110where
111 F: FnMut(I::Item) -> U,
112 U: IntoIterator<IntoIter: DoubleEndedIterator>,
113{
114 #[inline]
115 fn next_back(&mut self) -> Option<U::Item> {
116 self.inner.next_back()
117 }
118
119 #[inline]
120 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
121 where
122 Self: Sized,
123 Fold: FnMut(Acc, Self::Item) -> R,
124 R: Try<Output = Acc>,
125 {
126 self.inner.try_rfold(init, fold)
127 }
128
129 #[inline]
130 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
131 where
132 Fold: FnMut(Acc, Self::Item) -> Acc,
133 {
134 self.inner.rfold(init, fold)
135 }
136
137 #[inline]
138 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
139 self.inner.advance_back_by(n)
140 }
141}
142
143#[stable(feature = "fused", since = "1.26.0")]
144impl<I, U, F> FusedIterator for FlatMap<I, U, F>
145where
146 I: FusedIterator,
147 U: IntoIterator,
148 F: FnMut(I::Item) -> U,
149{
150}
151
152#[unstable(feature = "trusted_len", issue = "37572")]
153unsafe impl<I, U, F> TrustedLen for FlatMap<I, U, F>
154where
155 I: Iterator,
156 U: IntoIterator,
157 F: FnMut(I::Item) -> U,
158 FlattenCompat<Map<I, F>, <U as IntoIterator>::IntoIter>: TrustedLen,
159{
160}
161
162#[unstable(issue = "none", feature = "inplace_iteration")]
163unsafe impl<I, U, F> InPlaceIterable for FlatMap<I, U, F>
164where
165 I: InPlaceIterable,
166 U: BoundedSize + IntoIterator,
167{
168 const EXPAND_BY: Option<NonZeroUsize> = const {
169 match (I::EXPAND_BY, U::UPPER_BOUND) {
170 (Some(m: NonZero), Some(n: NonZero)) => m.checked_mul(n),
171 _ => None,
172 }
173 };
174 const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY;
175}
176
177#[unstable(issue = "none", feature = "inplace_iteration")]
178unsafe impl<I, U, F> SourceIter for FlatMap<I, U, F>
179where
180 I: SourceIter + TrustedFused,
181 U: IntoIterator,
182{
183 type Source = I::Source;
184
185 #[inline]
186 unsafe fn as_inner(&mut self) -> &mut I::Source {
187 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
188 unsafe { SourceIter::as_inner(&mut self.inner.iter) }
189 }
190}
191
192/// Marker trait for iterators/iterables which have a statically known upper
193/// bound of the number of items they can produce.
194///
195/// # Safety
196///
197/// Implementations must not yield more elements than indicated by UPPER_BOUND if it is `Some`.
198/// Used in specializations. Implementations must not be conditional on lifetimes or
199/// user-implementable traits.
200#[rustc_specialization_trait]
201#[unstable(issue = "none", feature = "inplace_iteration")]
202unsafe trait BoundedSize {
203 const UPPER_BOUND: Option<NonZeroUsize> = NonZeroUsize::new(1);
204}
205
206#[unstable(issue = "none", feature = "inplace_iteration")]
207unsafe impl<T> BoundedSize for Option<T> {}
208#[unstable(issue = "none", feature = "inplace_iteration")]
209unsafe impl<T> BoundedSize for option::IntoIter<T> {}
210#[unstable(issue = "none", feature = "inplace_iteration")]
211unsafe impl<T, U> BoundedSize for Result<T, U> {}
212#[unstable(issue = "none", feature = "inplace_iteration")]
213unsafe impl<T> BoundedSize for result::IntoIter<T> {}
214#[unstable(issue = "none", feature = "inplace_iteration")]
215unsafe impl<T> BoundedSize for Once<T> {}
216#[unstable(issue = "none", feature = "inplace_iteration")]
217unsafe impl<T> BoundedSize for OnceWith<T> {}
218#[unstable(issue = "none", feature = "inplace_iteration")]
219unsafe impl<T, const N: usize> BoundedSize for [T; N] {
220 const UPPER_BOUND: Option<NonZeroUsize> = NonZeroUsize::new(N);
221}
222#[unstable(issue = "none", feature = "inplace_iteration")]
223unsafe impl<T, const N: usize> BoundedSize for array::IntoIter<T, N> {
224 const UPPER_BOUND: Option<NonZeroUsize> = NonZeroUsize::new(N);
225}
226#[unstable(issue = "none", feature = "inplace_iteration")]
227unsafe impl<I: BoundedSize, P> BoundedSize for Filter<I, P> {
228 const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND;
229}
230#[unstable(issue = "none", feature = "inplace_iteration")]
231unsafe impl<I: BoundedSize, P> BoundedSize for FilterMap<I, P> {
232 const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND;
233}
234#[unstable(issue = "none", feature = "inplace_iteration")]
235unsafe impl<I: BoundedSize, F> BoundedSize for Map<I, F> {
236 const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND;
237}
238#[unstable(issue = "none", feature = "inplace_iteration")]
239unsafe impl<I: BoundedSize> BoundedSize for Copied<I> {
240 const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND;
241}
242#[unstable(issue = "none", feature = "inplace_iteration")]
243unsafe impl<I: BoundedSize> BoundedSize for Cloned<I> {
244 const UPPER_BOUND: Option<NonZeroUsize> = I::UPPER_BOUND;
245}
246
247/// An iterator that flattens one level of nesting in an iterator of things
248/// that can be turned into iterators.
249///
250/// This `struct` is created by the [`flatten`] method on [`Iterator`]. See its
251/// documentation for more.
252///
253/// [`flatten`]: Iterator::flatten()
254#[must_use = "iterators are lazy and do nothing unless consumed"]
255#[stable(feature = "iterator_flatten", since = "1.29.0")]
256pub struct Flatten<I: Iterator<Item: IntoIterator>> {
257 inner: FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>,
258}
259
260impl<I: Iterator<Item: IntoIterator>> Flatten<I> {
261 pub(in super::super) fn new(iter: I) -> Flatten<I> {
262 Flatten { inner: FlattenCompat::new(iter) }
263 }
264}
265
266#[stable(feature = "iterator_flatten", since = "1.29.0")]
267impl<I, U> fmt::Debug for Flatten<I>
268where
269 I: fmt::Debug + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
270 U: fmt::Debug + Iterator,
271{
272 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
273 f.debug_struct("Flatten").field(name:"inner", &self.inner).finish()
274 }
275}
276
277#[stable(feature = "iterator_flatten", since = "1.29.0")]
278impl<I, U> Clone for Flatten<I>
279where
280 I: Clone + Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
281 U: Clone + Iterator,
282{
283 fn clone(&self) -> Self {
284 Flatten { inner: self.inner.clone() }
285 }
286}
287
288#[stable(feature = "iterator_flatten", since = "1.29.0")]
289impl<I, U> Iterator for Flatten<I>
290where
291 I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
292 U: Iterator,
293{
294 type Item = U::Item;
295
296 #[inline]
297 fn next(&mut self) -> Option<U::Item> {
298 self.inner.next()
299 }
300
301 #[inline]
302 fn size_hint(&self) -> (usize, Option<usize>) {
303 self.inner.size_hint()
304 }
305
306 #[inline]
307 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
308 where
309 Self: Sized,
310 Fold: FnMut(Acc, Self::Item) -> R,
311 R: Try<Output = Acc>,
312 {
313 self.inner.try_fold(init, fold)
314 }
315
316 #[inline]
317 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
318 where
319 Fold: FnMut(Acc, Self::Item) -> Acc,
320 {
321 self.inner.fold(init, fold)
322 }
323
324 #[inline]
325 fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
326 self.inner.advance_by(n)
327 }
328
329 #[inline]
330 fn count(self) -> usize {
331 self.inner.count()
332 }
333
334 #[inline]
335 fn last(self) -> Option<Self::Item> {
336 self.inner.last()
337 }
338}
339
340#[stable(feature = "iterator_flatten", since = "1.29.0")]
341impl<I, U> DoubleEndedIterator for Flatten<I>
342where
343 I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
344 U: DoubleEndedIterator,
345{
346 #[inline]
347 fn next_back(&mut self) -> Option<U::Item> {
348 self.inner.next_back()
349 }
350
351 #[inline]
352 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
353 where
354 Self: Sized,
355 Fold: FnMut(Acc, Self::Item) -> R,
356 R: Try<Output = Acc>,
357 {
358 self.inner.try_rfold(init, fold)
359 }
360
361 #[inline]
362 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
363 where
364 Fold: FnMut(Acc, Self::Item) -> Acc,
365 {
366 self.inner.rfold(init, fold)
367 }
368
369 #[inline]
370 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
371 self.inner.advance_back_by(n)
372 }
373}
374
375#[stable(feature = "iterator_flatten", since = "1.29.0")]
376impl<I, U> FusedIterator for Flatten<I>
377where
378 I: FusedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
379 U: Iterator,
380{
381}
382
383#[unstable(feature = "trusted_len", issue = "37572")]
384unsafe impl<I> TrustedLen for Flatten<I>
385where
386 I: Iterator<Item: IntoIterator>,
387 FlattenCompat<I, <I::Item as IntoIterator>::IntoIter>: TrustedLen,
388{
389}
390
391#[unstable(issue = "none", feature = "inplace_iteration")]
392unsafe impl<I> InPlaceIterable for Flatten<I>
393where
394 I: InPlaceIterable + Iterator,
395 <I as Iterator>::Item: IntoIterator + BoundedSize,
396{
397 const EXPAND_BY: Option<NonZeroUsize> = const {
398 match (I::EXPAND_BY, I::Item::UPPER_BOUND) {
399 (Some(m: NonZero), Some(n: NonZero)) => m.checked_mul(n),
400 _ => None,
401 }
402 };
403 const MERGE_BY: Option<NonZeroUsize> = I::MERGE_BY;
404}
405
406#[unstable(issue = "none", feature = "inplace_iteration")]
407unsafe impl<I> SourceIter for Flatten<I>
408where
409 I: SourceIter + TrustedFused + Iterator,
410 <I as Iterator>::Item: IntoIterator,
411{
412 type Source = I::Source;
413
414 #[inline]
415 unsafe fn as_inner(&mut self) -> &mut I::Source {
416 // SAFETY: unsafe function forwarding to unsafe function with the same requirements
417 unsafe { SourceIter::as_inner(&mut self.inner.iter) }
418 }
419}
420
421#[stable(feature = "default_iters", since = "1.70.0")]
422impl<I> Default for Flatten<I>
423where
424 I: Default + Iterator<Item: IntoIterator>,
425{
426 /// Creates a `Flatten` iterator from the default value of `I`.
427 ///
428 /// ```
429 /// # use core::slice;
430 /// # use std::iter::Flatten;
431 /// let iter: Flatten<slice::Iter<'_, [u8; 4]>> = Default::default();
432 /// assert_eq!(iter.count(), 0);
433 /// ```
434 fn default() -> Self {
435 Flatten::new(iter:Default::default())
436 }
437}
438
439/// Real logic of both `Flatten` and `FlatMap` which simply delegate to
440/// this type.
441#[derive(Clone, Debug)]
442#[unstable(feature = "trusted_len", issue = "37572")]
443struct FlattenCompat<I, U> {
444 iter: Fuse<I>,
445 frontiter: Option<U>,
446 backiter: Option<U>,
447}
448impl<I, U> FlattenCompat<I, U>
449where
450 I: Iterator,
451{
452 /// Adapts an iterator by flattening it, for use in `flatten()` and `flat_map()`.
453 fn new(iter: I) -> FlattenCompat<I, U> {
454 FlattenCompat { iter: iter.fuse(), frontiter: None, backiter: None }
455 }
456}
457
458impl<I, U> FlattenCompat<I, U>
459where
460 I: Iterator<Item: IntoIterator<IntoIter = U>>,
461{
462 /// Folds the inner iterators into an accumulator by applying an operation.
463 ///
464 /// Folds over the inner iterators, not over their elements. Is used by the `fold`, `count`,
465 /// and `last` methods.
466 #[inline]
467 fn iter_fold<Acc, Fold>(self, mut acc: Acc, mut fold: Fold) -> Acc
468 where
469 Fold: FnMut(Acc, U) -> Acc,
470 {
471 #[inline]
472 fn flatten<T: IntoIterator, Acc>(
473 fold: &mut impl FnMut(Acc, T::IntoIter) -> Acc,
474 ) -> impl FnMut(Acc, T) -> Acc + '_ {
475 move |acc, iter| fold(acc, iter.into_iter())
476 }
477
478 if let Some(iter) = self.frontiter {
479 acc = fold(acc, iter);
480 }
481
482 acc = self.iter.fold(acc, flatten(&mut fold));
483
484 if let Some(iter) = self.backiter {
485 acc = fold(acc, iter);
486 }
487
488 acc
489 }
490
491 /// Folds over the inner iterators as long as the given function returns successfully,
492 /// always storing the most recent inner iterator in `self.frontiter`.
493 ///
494 /// Folds over the inner iterators, not over their elements. Is used by the `try_fold` and
495 /// `advance_by` methods.
496 #[inline]
497 fn iter_try_fold<Acc, Fold, R>(&mut self, mut acc: Acc, mut fold: Fold) -> R
498 where
499 Fold: FnMut(Acc, &mut U) -> R,
500 R: Try<Output = Acc>,
501 {
502 #[inline]
503 fn flatten<'a, T: IntoIterator, Acc, R: Try<Output = Acc>>(
504 frontiter: &'a mut Option<T::IntoIter>,
505 fold: &'a mut impl FnMut(Acc, &mut T::IntoIter) -> R,
506 ) -> impl FnMut(Acc, T) -> R + 'a {
507 move |acc, iter| fold(acc, frontiter.insert(iter.into_iter()))
508 }
509
510 if let Some(iter) = &mut self.frontiter {
511 acc = fold(acc, iter)?;
512 }
513 self.frontiter = None;
514
515 acc = self.iter.try_fold(acc, flatten(&mut self.frontiter, &mut fold))?;
516 self.frontiter = None;
517
518 if let Some(iter) = &mut self.backiter {
519 acc = fold(acc, iter)?;
520 }
521 self.backiter = None;
522
523 try { acc }
524 }
525}
526
527impl<I, U> FlattenCompat<I, U>
528where
529 I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U>>,
530{
531 /// Folds the inner iterators into an accumulator by applying an operation, starting form the
532 /// back.
533 ///
534 /// Folds over the inner iterators, not over their elements. Is used by the `rfold` method.
535 #[inline]
536 fn iter_rfold<Acc, Fold>(self, mut acc: Acc, mut fold: Fold) -> Acc
537 where
538 Fold: FnMut(Acc, U) -> Acc,
539 {
540 #[inline]
541 fn flatten<T: IntoIterator, Acc>(
542 fold: &mut impl FnMut(Acc, T::IntoIter) -> Acc,
543 ) -> impl FnMut(Acc, T) -> Acc + '_ {
544 move |acc, iter| fold(acc, iter.into_iter())
545 }
546
547 if let Some(iter) = self.backiter {
548 acc = fold(acc, iter);
549 }
550
551 acc = self.iter.rfold(acc, flatten(&mut fold));
552
553 if let Some(iter) = self.frontiter {
554 acc = fold(acc, iter);
555 }
556
557 acc
558 }
559
560 /// Folds over the inner iterators in reverse order as long as the given function returns
561 /// successfully, always storing the most recent inner iterator in `self.backiter`.
562 ///
563 /// Folds over the inner iterators, not over their elements. Is used by the `try_rfold` and
564 /// `advance_back_by` methods.
565 #[inline]
566 fn iter_try_rfold<Acc, Fold, R>(&mut self, mut acc: Acc, mut fold: Fold) -> R
567 where
568 Fold: FnMut(Acc, &mut U) -> R,
569 R: Try<Output = Acc>,
570 {
571 #[inline]
572 fn flatten<'a, T: IntoIterator, Acc, R: Try>(
573 backiter: &'a mut Option<T::IntoIter>,
574 fold: &'a mut impl FnMut(Acc, &mut T::IntoIter) -> R,
575 ) -> impl FnMut(Acc, T) -> R + 'a {
576 move |acc, iter| fold(acc, backiter.insert(iter.into_iter()))
577 }
578
579 if let Some(iter) = &mut self.backiter {
580 acc = fold(acc, iter)?;
581 }
582 self.backiter = None;
583
584 acc = self.iter.try_rfold(acc, flatten(&mut self.backiter, &mut fold))?;
585 self.backiter = None;
586
587 if let Some(iter) = &mut self.frontiter {
588 acc = fold(acc, iter)?;
589 }
590 self.frontiter = None;
591
592 try { acc }
593 }
594}
595
596impl<I, U> Iterator for FlattenCompat<I, U>
597where
598 I: Iterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
599 U: Iterator,
600{
601 type Item = U::Item;
602
603 #[inline]
604 fn next(&mut self) -> Option<U::Item> {
605 loop {
606 if let elt @ Some(_) = and_then_or_clear(&mut self.frontiter, Iterator::next) {
607 return elt;
608 }
609 match self.iter.next() {
610 None => return and_then_or_clear(&mut self.backiter, Iterator::next),
611 Some(inner) => self.frontiter = Some(inner.into_iter()),
612 }
613 }
614 }
615
616 #[inline]
617 fn size_hint(&self) -> (usize, Option<usize>) {
618 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), U::size_hint);
619 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), U::size_hint);
620 let lo = flo.saturating_add(blo);
621
622 if let Some(fixed_size) = <<I as Iterator>::Item as ConstSizeIntoIterator>::size() {
623 let (lower, upper) = self.iter.size_hint();
624
625 let lower = lower.saturating_mul(fixed_size).saturating_add(lo);
626 let upper =
627 try { fhi?.checked_add(bhi?)?.checked_add(fixed_size.checked_mul(upper?)?)? };
628
629 return (lower, upper);
630 }
631
632 match (self.iter.size_hint(), fhi, bhi) {
633 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(b)),
634 _ => (lo, None),
635 }
636 }
637
638 #[inline]
639 fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
640 where
641 Self: Sized,
642 Fold: FnMut(Acc, Self::Item) -> R,
643 R: Try<Output = Acc>,
644 {
645 #[inline]
646 fn flatten<U: Iterator, Acc, R: Try<Output = Acc>>(
647 mut fold: impl FnMut(Acc, U::Item) -> R,
648 ) -> impl FnMut(Acc, &mut U) -> R {
649 move |acc, iter| iter.try_fold(acc, &mut fold)
650 }
651
652 self.iter_try_fold(init, flatten(fold))
653 }
654
655 #[inline]
656 fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
657 where
658 Fold: FnMut(Acc, Self::Item) -> Acc,
659 {
660 #[inline]
661 fn flatten<U: Iterator, Acc>(
662 mut fold: impl FnMut(Acc, U::Item) -> Acc,
663 ) -> impl FnMut(Acc, U) -> Acc {
664 move |acc, iter| iter.fold(acc, &mut fold)
665 }
666
667 self.iter_fold(init, flatten(fold))
668 }
669
670 #[inline]
671 #[rustc_inherit_overflow_checks]
672 fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
673 #[inline]
674 #[rustc_inherit_overflow_checks]
675 fn advance<U: Iterator>(n: usize, iter: &mut U) -> ControlFlow<(), usize> {
676 match iter.advance_by(n) {
677 Ok(()) => ControlFlow::Break(()),
678 Err(remaining) => ControlFlow::Continue(remaining.get()),
679 }
680 }
681
682 match self.iter_try_fold(n, advance) {
683 ControlFlow::Continue(remaining) => NonZeroUsize::new(remaining).map_or(Ok(()), Err),
684 _ => Ok(()),
685 }
686 }
687
688 #[inline]
689 fn count(self) -> usize {
690 #[inline]
691 #[rustc_inherit_overflow_checks]
692 fn count<U: Iterator>(acc: usize, iter: U) -> usize {
693 acc + iter.count()
694 }
695
696 self.iter_fold(0, count)
697 }
698
699 #[inline]
700 fn last(self) -> Option<Self::Item> {
701 #[inline]
702 fn last<U: Iterator>(last: Option<U::Item>, iter: U) -> Option<U::Item> {
703 iter.last().or(last)
704 }
705
706 self.iter_fold(None, last)
707 }
708}
709
710impl<I, U> DoubleEndedIterator for FlattenCompat<I, U>
711where
712 I: DoubleEndedIterator<Item: IntoIterator<IntoIter = U, Item = U::Item>>,
713 U: DoubleEndedIterator,
714{
715 #[inline]
716 fn next_back(&mut self) -> Option<U::Item> {
717 loop {
718 if let elt @ Some(_) = and_then_or_clear(&mut self.backiter, |b| b.next_back()) {
719 return elt;
720 }
721 match self.iter.next_back() {
722 None => return and_then_or_clear(&mut self.frontiter, |f| f.next_back()),
723 Some(inner) => self.backiter = Some(inner.into_iter()),
724 }
725 }
726 }
727
728 #[inline]
729 fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
730 where
731 Self: Sized,
732 Fold: FnMut(Acc, Self::Item) -> R,
733 R: Try<Output = Acc>,
734 {
735 #[inline]
736 fn flatten<U: DoubleEndedIterator, Acc, R: Try<Output = Acc>>(
737 mut fold: impl FnMut(Acc, U::Item) -> R,
738 ) -> impl FnMut(Acc, &mut U) -> R {
739 move |acc, iter| iter.try_rfold(acc, &mut fold)
740 }
741
742 self.iter_try_rfold(init, flatten(fold))
743 }
744
745 #[inline]
746 fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
747 where
748 Fold: FnMut(Acc, Self::Item) -> Acc,
749 {
750 #[inline]
751 fn flatten<U: DoubleEndedIterator, Acc>(
752 mut fold: impl FnMut(Acc, U::Item) -> Acc,
753 ) -> impl FnMut(Acc, U) -> Acc {
754 move |acc, iter| iter.rfold(acc, &mut fold)
755 }
756
757 self.iter_rfold(init, flatten(fold))
758 }
759
760 #[inline]
761 #[rustc_inherit_overflow_checks]
762 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
763 #[inline]
764 #[rustc_inherit_overflow_checks]
765 fn advance<U: DoubleEndedIterator>(n: usize, iter: &mut U) -> ControlFlow<(), usize> {
766 match iter.advance_back_by(n) {
767 Ok(()) => ControlFlow::Break(()),
768 Err(remaining) => ControlFlow::Continue(remaining.get()),
769 }
770 }
771
772 match self.iter_try_rfold(n, advance) {
773 ControlFlow::Continue(remaining) => NonZeroUsize::new(remaining).map_or(Ok(()), Err),
774 _ => Ok(()),
775 }
776 }
777}
778
779unsafe impl<const N: usize, I, T> TrustedLen
780 for FlattenCompat<I, <[T; N] as IntoIterator>::IntoIter>
781where
782 I: TrustedLen<Item = [T; N]>,
783{
784}
785
786unsafe impl<'a, const N: usize, I, T> TrustedLen
787 for FlattenCompat<I, <&'a [T; N] as IntoIterator>::IntoIter>
788where
789 I: TrustedLen<Item = &'a [T; N]>,
790{
791}
792
793unsafe impl<'a, const N: usize, I, T> TrustedLen
794 for FlattenCompat<I, <&'a mut [T; N] as IntoIterator>::IntoIter>
795where
796 I: TrustedLen<Item = &'a mut [T; N]>,
797{
798}
799
800trait ConstSizeIntoIterator: IntoIterator {
801 // FIXME(#31844): convert to an associated const once specialization supports that
802 fn size() -> Option<usize>;
803}
804
805impl<T> ConstSizeIntoIterator for T
806where
807 T: IntoIterator,
808{
809 #[inline]
810 default fn size() -> Option<usize> {
811 None
812 }
813}
814
815impl<T, const N: usize> ConstSizeIntoIterator for [T; N] {
816 #[inline]
817 fn size() -> Option<usize> {
818 Some(N)
819 }
820}
821
822impl<T, const N: usize> ConstSizeIntoIterator for &[T; N] {
823 #[inline]
824 fn size() -> Option<usize> {
825 Some(N)
826 }
827}
828
829impl<T, const N: usize> ConstSizeIntoIterator for &mut [T; N] {
830 #[inline]
831 fn size() -> Option<usize> {
832 Some(N)
833 }
834}
835
836#[inline]
837fn and_then_or_clear<T, U>(opt: &mut Option<T>, f: impl FnOnce(&mut T) -> Option<U>) -> Option<U> {
838 let x: Option = f(opt.as_mut()?);
839 if x.is_none() {
840 *opt = None;
841 }
842 x
843}
844