infinite_iterator/
lib.rs

1//! This crate provides a trait,
2//! `InfiniteIterator`,
3//! used to represent an iterator for which [`next`]
4//! can never return `None`.
5//!
6//! It additionally provides a macro, `ifor!`,
7//! which is identical a for loop
8//! except it supports breaking with a value
9//! when used on an infinite iterator.
10//!
11//! [`next`]: https://doc.rust-lang.org/stable/std/iter/trait.Iterator.html#tymethod.next
12#![no_std]
13
14#[cfg(feature = "std")]
15extern crate std;
16
17#[cfg(feature = "alloc")]
18extern crate alloc;
19
20use core::iter;
21
22/// An [`Iterator`] that never ends.
23///
24/// # Invariants
25///
26/// For this trait to be correctly implemented,
27/// the following invariants must be upheld:
28/// 1. `Some(iter.next_infinite())` must always give the same result as `iter.next()`.
29/// 2. No default-implemented iterator methods may be overriden
30///     to have visibly different behaviour
31///     than their default implementations.
32/// 3. `size_hint().1` must always be `None`.
33/// 4. The type must not implement [`ExactSizeIterator`].
34///
35/// If any of the above invariants are violated,
36/// the behaviour of any code that uses the iterator is unspecified
37/// (i.e. it may panic, abort or give wrong results) —
38/// however, because `InfiniteIterator` is not an `unsafe trait`
39/// it still must not invoke Undefined Behaviour.
40#[must_use = "iterators are lazy and do nothing unless consumed"]
41pub trait InfiniteIterator: Iterator {
42    /// Like [`Iterator::next`],
43    /// but never returning [`None`] because the iterator never ends.
44    fn next_infinite(&mut self) -> Self::Item;
45
46    /// Like [`Iterator::for_each`],
47    /// but it never returns because the iterator never ends.
48    ///
49    /// # Examples
50    ///
51    /// ```
52    /// use infinite_iterator::InfiniteIterator;
53    ///
54    /// fn run() -> ! {
55    ///     (0..).for_each_infinite(|num| {
56    ///         println!("{num}");
57    ///         std::thread::sleep(std::time::Duration::from_secs(5));
58    ///     })
59    /// }
60    /// ```
61    fn for_each_infinite<F: FnMut(Self::Item)>(mut self, mut f: F) -> !
62    where
63        Self: Sized,
64    {
65        loop {
66            f(self.next_infinite());
67        }
68    }
69
70    /// Like [`Iterator::find`],
71    /// but it is guaranteed to find an item
72    /// (or loop forever)
73    /// because the iterator is infinite.
74    ///
75    /// # Examples
76    ///
77    /// ```
78    /// use infinite_iterator::InfiniteIterator;
79    ///
80    /// assert_eq!((5..).find_infinite(|&num| num > 10), 11);
81    /// ```
82    fn find_infinite<P>(&mut self, mut predicate: P) -> Self::Item
83    where
84        Self: Sized,
85        P: FnMut(&Self::Item) -> bool,
86    {
87        loop {
88            let item = self.next_infinite();
89            if predicate(&item) {
90                break item;
91            }
92        }
93    }
94
95    /// Like [`Iterator::find_map`],
96    /// but it is guaranteed to find an item
97    /// (or loop forever)
98    /// because the iterator is infinite.
99    ///
100    /// # Examples
101    ///
102    /// ```
103    /// use infinite_iterator::InfiniteIterator;
104    ///
105    /// assert_eq!((5_u32..).step_by(3).find_map_infinite(|num| num.checked_sub(10)), 1);
106    /// ```
107    fn find_map_infinite<B, F>(&mut self, mut f: F) -> B
108    where
109        Self: Sized,
110        F: FnMut(Self::Item) -> Option<B>,
111    {
112        loop {
113            if let Some(mapped) = f(self.next_infinite()) {
114                break mapped;
115            }
116        }
117    }
118
119    /// Like [`Iterator::position`],
120    /// but it is guaranteed to find an item
121    /// (or loop forever)
122    /// because the iterator is infinite.
123    ///
124    /// # Examples
125    ///
126    /// ```
127    /// use infinite_iterator::InfiniteIterator;
128    ///
129    /// assert_eq!((5..).position_infinite(|num| num > 10), 6);
130    /// ```
131    fn position_infinite<P>(&mut self, mut predicate: P) -> usize
132    where
133        Self: Sized,
134        P: FnMut(Self::Item) -> bool,
135    {
136        let mut i = 0;
137        loop {
138            if predicate(self.next_infinite()) {
139                break i;
140            }
141            i += 1;
142        }
143    }
144}
145
146impl<I: ?Sized + InfiniteIterator> InfiniteIterator for &mut I {
147    fn next_infinite(&mut self) -> Self::Item {
148        (**self).next_infinite()
149    }
150}
151
152#[cfg(feature = "alloc")]
153impl<I: ?Sized + InfiniteIterator> InfiniteIterator for alloc::boxed::Box<I> {
154    fn next_infinite(&mut self) -> Self::Item {
155        (**self).next_infinite()
156    }
157}
158
159impl<'item, I, T> InfiniteIterator for iter::Cloned<I>
160where
161    T: 'item + Clone,
162    I: InfiniteIterator<Item = &'item T>,
163{
164    fn next_infinite(&mut self) -> Self::Item {
165        self.next().unwrap()
166    }
167}
168
169impl<'item, I, T> InfiniteIterator for iter::Copied<I>
170where
171    T: 'item + Copy,
172    I: InfiniteIterator<Item = &'item T>,
173{
174    fn next_infinite(&mut self) -> Self::Item {
175        self.next().unwrap()
176    }
177}
178
179impl<A: Clone> InfiniteIterator for iter::Repeat<A> {
180    fn next_infinite(&mut self) -> Self::Item {
181        // SAFETY: `Repeat` never ends.
182        unsafe { self.next().unwrap_unchecked() }
183    }
184}
185
186impl<F: FnMut() -> A, A> InfiniteIterator for iter::RepeatWith<F> {
187    fn next_infinite(&mut self) -> Self::Item {
188        unsafe { self.next().unwrap_unchecked() }
189    }
190}
191
192impl<A, B> InfiniteIterator for iter::Chain<A, B>
193where
194    A: Iterator,
195    B: InfiniteIterator<Item = A::Item>,
196{
197    fn next_infinite(&mut self) -> Self::Item {
198        self.next().unwrap()
199    }
200}
201
202impl<A, B> InfiniteIterator for iter::Zip<A, B>
203where
204    A: InfiniteIterator,
205    B: InfiniteIterator,
206{
207    fn next_infinite(&mut self) -> Self::Item {
208        self.next().unwrap()
209    }
210}
211
212impl<I, P> InfiniteIterator for iter::Filter<I, P>
213where
214    I: InfiniteIterator,
215    P: FnMut(&I::Item) -> bool,
216{
217    fn next_infinite(&mut self) -> Self::Item {
218        self.next().unwrap()
219    }
220}
221
222impl<B, I, F> InfiniteIterator for iter::FilterMap<I, F>
223where
224    I: InfiniteIterator,
225    F: FnMut(I::Item) -> Option<B>,
226{
227    fn next_infinite(&mut self) -> Self::Item {
228        self.next().unwrap()
229    }
230}
231
232impl<B, I, F> InfiniteIterator for iter::Map<I, F>
233where
234    I: InfiniteIterator,
235    F: FnMut(I::Item) -> Option<B>,
236{
237    fn next_infinite(&mut self) -> Self::Item {
238        self.next().unwrap()
239    }
240}
241
242// Require `InfiniteIterator` to prevent empty iterators
243impl<I: Clone + InfiniteIterator> InfiniteIterator for iter::Cycle<I> {
244    fn next_infinite(&mut self) -> Self::Item {
245        self.next().unwrap()
246    }
247}
248
249impl<I: InfiniteIterator> InfiniteIterator for iter::Enumerate<I> {
250    fn next_infinite(&mut self) -> Self::Item {
251        self.next().unwrap()
252    }
253}
254
255impl<I: InfiniteIterator> InfiniteIterator for iter::Fuse<I> {
256    fn next_infinite(&mut self) -> Self::Item {
257        self.next().unwrap()
258    }
259}
260
261impl<I: InfiniteIterator> InfiniteIterator for iter::Peekable<I> {
262    fn next_infinite(&mut self) -> Self::Item {
263        self.next().unwrap()
264    }
265}
266
267/// An extension trait providing extra methods to [`iter::Peekable`]
268/// when the underlying iterator never ends.
269///
270/// This trait is sealed;
271/// it can only be implemented on [`iter::Peekable`].
272pub trait PeekableExt: peekable_ext::Sealed {
273    /// Like [`iter::Peekable::peek`],
274    /// but always returning a reference
275    /// because the underlying iterator never ends.
276    fn peek_infinite(&mut self) -> &Self::Item;
277
278    /// Like [`iter::Peekable::peek_mut`],
279    /// but always returning a unique reference
280    /// because the underlying iterator never ends.
281    fn peek_infinite_mut(&mut self) -> &mut Self::Item;
282}
283
284mod peekable_ext {
285    pub trait Sealed: Sized + Iterator {}
286}
287
288impl<I: InfiniteIterator> peekable_ext::Sealed for iter::Peekable<I> {}
289impl<I: InfiniteIterator> PeekableExt for iter::Peekable<I> {
290    fn peek_infinite(&mut self) -> &Self::Item {
291        self.peek().unwrap()
292    }
293
294    fn peek_infinite_mut(&mut self) -> &mut Self::Item {
295        self.peek_mut().unwrap()
296    }
297}
298
299impl<I: InfiniteIterator> InfiniteIterator for iter::Skip<I> {
300    fn next_infinite(&mut self) -> Self::Item {
301        self.next().unwrap()
302    }
303}
304
305impl<I, P> InfiniteIterator for iter::SkipWhile<I, P>
306where
307    I: InfiniteIterator,
308    P: FnMut(&I::Item) -> bool,
309{
310    fn next_infinite(&mut self) -> Self::Item {
311        self.next().unwrap()
312    }
313}
314
315impl<I: InfiniteIterator> InfiniteIterator for iter::StepBy<I> {
316    fn next_infinite(&mut self) -> Self::Item {
317        self.next().unwrap()
318    }
319}
320
321impl<I: InfiniteIterator, F> InfiniteIterator for iter::Inspect<I, F>
322where
323    I: InfiniteIterator,
324    F: FnMut(&I::Item),
325{
326    fn next_infinite(&mut self) -> Self::Item {
327        self.next().unwrap()
328    }
329}
330
331impl<I> InfiniteIterator for iter::Flatten<I>
332where
333    I: InfiniteIterator,
334    I::Item: IntoIterator,
335{
336    fn next_infinite(&mut self) -> Self::Item {
337        self.next().unwrap()
338    }
339}
340
341impl<I, U, F> InfiniteIterator for iter::FlatMap<I, U, F>
342where
343    I: InfiniteIterator,
344    U: IntoIterator,
345    F: FnMut(I::Item) -> U,
346{
347    fn next_infinite(&mut self) -> Self::Item {
348        self.next().unwrap()
349    }
350}
351
352impl<A> InfiniteIterator for core::ops::RangeFrom<A>
353where
354    core::ops::RangeFrom<A>: Iterator,
355{
356    fn next_infinite(&mut self) -> Self::Item {
357        // SAFETY: The `RangeFrom` iterator never ends
358        unsafe { self.next().unwrap_unchecked() }
359    }
360}
361
362#[cfg(feature = "std")]
363impl InfiniteIterator for std::net::Incoming<'_> {
364    fn next_infinite(&mut self) -> Self::Item {
365        // SAFETY: The Incoming iterator never ends.
366        unsafe { self.next().unwrap_unchecked() }
367    }
368}
369
370#[cfg(all(feature = "std", unix))]
371impl InfiniteIterator for std::os::unix::net::Incoming<'_> {
372    fn next_infinite(&mut self) -> Self::Item {
373        // SAFETY: The Incoming iterator never ends
374        unsafe { self.next().unwrap_unchecked() }
375    }
376}
377
378/// An extension of `for in` loops with better support for infinite iterators.
379///
380/// This macro presents a _superset_ of regular `for` loops:
381/// it works both with finite and infinite iterators.
382///
383/// # Examples
384///
385/// Use with a finite iterator:
386///
387/// ```
388/// use infinite_iterator::ifor;
389///
390/// ifor!(item in [1, 2, 3] {
391///     println!("{item}");
392/// });
393/// ```
394///
395/// Use with an infinite iterator:
396///
397/// ```
398/// use infinite_iterator::ifor;
399///
400/// # fn run() -> ! {
401/// ifor!(item in 0.. {
402///     println!("{item}");
403///     std::thread::sleep(std::time::Duration::from_secs(5));
404/// })
405/// # }
406/// ```
407///
408/// Infinite iterators additionally support breaking with a value:
409///
410/// ```
411/// use infinite_iterator::ifor;
412///
413/// let item = ifor!(item in 0.. {
414///     if item > 10 {
415///         break item;
416///     }
417/// });
418///
419/// assert_eq!(item, 11);
420/// ```
421///
422/// You can use loop labels with an `ifor!` too,
423/// as long as you write out the keyword `for`:
424///
425/// ```
426/// use infinite_iterator::ifor;
427///
428/// ifor!('outer: for a in 0..10 {
429///     ifor!('inner: for b in 0..10 {
430///         println!("{a}, {b}");
431///         if a + b > 16 {
432///             break 'outer;
433///         }
434///     });
435/// });
436/// ```
437#[macro_export]
438macro_rules! ifor {
439    ($($label:lifetime:)? for $pat:pat in $($rest:tt)*) => {
440        $crate::__ifor_inner!($($label:)? for $pat in () $($rest)*)
441    };
442    ($pat:pat in $($rest:tt)*) => {
443        $crate::__ifor_inner!(for $pat in () $($rest)*)
444    };
445}
446
447// Not public API.
448#[doc(hidden)]
449#[macro_export]
450macro_rules! __ifor_inner {
451    ($($label:lifetime:)? for $pat:pat in ($expr:expr) $block:block) => {
452        match $crate::__private::IntoIterator::into_iter($expr) {
453            iter => {
454                let mut iter = $crate::__private::MaybeInfinite(iter);
455                $($label:)? loop {
456                    let $pat = {
457                        use $crate::__private::TryNextFallback;
458                        match iter.try_next() {
459                            $crate::__private::Ok(item) => item,
460                            $crate::__private::Err(breakable) => {
461                                break breakable.into_break()
462                            },
463                        }
464                    };
465                    $block
466                }
467            }
468        }
469    };
470    ($($label:lifetime:)? for $pat:pat in () $block:block) => {
471        $crate::__private::compile_error!("no expression provided to `ifor!`")
472    };
473    ($($label:lifetime:)? for $pat:pat in ($($expr:tt)*) $first:tt $($rest:tt)*) => {
474        $crate::__ifor_inner!($($label:)? for $pat in ($($expr)* $first) $($rest)*)
475    };
476}
477
478// Not public API.
479#[doc(hidden)]
480pub mod __private {
481    use crate::InfiniteIterator;
482
483    pub use core::compile_error;
484    pub use Err;
485    pub use IntoIterator;
486    pub use Ok;
487
488    pub struct MaybeInfinite<I>(pub I);
489
490    impl<I: InfiniteIterator> MaybeInfinite<I> {
491        pub fn try_next(&mut self) -> Result<I::Item, NeverBreak> {
492            Ok(self.0.next_infinite())
493        }
494    }
495
496    pub trait TryNextFallback: Sized {
497        type Item;
498        fn try_next(&mut self) -> Result<Self::Item, CanBreak>;
499    }
500    impl<I: Iterator> TryNextFallback for MaybeInfinite<I> {
501        type Item = I::Item;
502        fn try_next(&mut self) -> Result<Self::Item, CanBreak> {
503            self.0.next().ok_or(CanBreak)
504        }
505    }
506
507    pub enum NeverBreak {}
508    impl NeverBreak {
509        pub fn into_break(self) -> ! {
510            match self {}
511        }
512    }
513
514    pub struct CanBreak;
515    impl CanBreak {
516        pub fn into_break(self) {}
517    }
518}
infinite_iterator/lib.rs

infinite_iterator/
lib.rs
