iterator_ilp/
lib.rs

1//! This crate implements an [`Iterator`] extension that provides
2//! instruction-parallel reductions
3//!
4//! # Motivation
5//!
6//! Have you ever wondered why `Iterator::sum()` performs so poorly on
7//! floating-point data?
8//!
9//! On my machine, a benchmark of summing the elements of a `Vec<f32>` that fits
10//! in the CPU's L1d cache (which is a precondition for maximal computation
11//! performance) sums about a billion numbers per second. This may seem
12//! reasonable until you realize that modern CPUs have multi-GHz clock rates,
13//! can process [multiple instructions per clock
14//! cycle](https://en.wikipedia.org/wiki/Superscalar_processor), and can sum
15//! [multiple floating-point numbers per
16//! instruction](https://en.wikipedia.org/wiki/Single_instruction,_multiple_data).
17//! Then you come to the realization that the orders of magnitude aren't right.
18//!
19//! The problem lies not in the implementation of `Iterator::sum()`, but in its
20//! definition. This code...
21//!
22//! ```
23//! # let floats = [0.0; 8192];
24//! let sum = floats.iter().sum::<f32>();
25//! ```
26//!
27//! ...correctly compiles down to the same assembly as that loop...
28//!
29//! ```
30//! # let floats = [0.0; 8192];
31//! let mut sum = 0.0;
32//! for &float in &floats {
33//!     sum += float;
34//! }
35//! ```
36//!
37//! ...but that loop itself isn't right for modern hardware, because it does not
38//! expose enough [instruction-level parallelism
39//! (ILP)](https://en.wikipedia.org/wiki/Instruction-level_parallelism).
40//!
41//! To give some context, the Rust compiler does not allow itself to reorder
42//! floating-point operations with respect to what the user wrote. This is a
43//! good thing in general because floating-point arithmetic is not
44//! [associative](https://en.wikipedia.org/wiki/Associative_property), which
45//! means such optimizations would make program output nondeterministic (it
46//! depends on what compiler optimizations were applied) and could break the
47//! [numerical stability](https://en.wikipedia.org/wiki/Numerical_stability) of
48//! some trickier algorithms.
49//!
50//! But in the case of the loop above, it also means that whatever optimizations
51//! are applied, the final code must only use one accumulator, and sum the first
52//! number into that accumulator, then the second number, then the third one...
53//!
54//! Doing so turns our whole program into a gigantic dependency chain of
55//! scalar floating-point operations, with no opportunities for compilers or
56//! hardware to extract parallelism. Without parallelism, hardware capabilities
57//! for small-scale parallelism go to waste, and execution speed becomes limited
58//! by the CPU's addition latency (how much time it takes to compute one
59//! addition) rather than its addition throughput (how many unrelated additions
60//! it can compute per second).
61//!
62//! This problem is not unique to `Iterator::sum()`, or even to floating-point
63//! data. All iterator methods that perform data reduction (take an iterator of
64//! elements and produce a single result) are affected by this problem to some
65//! degree. All it takes is an operation whose semantics depend on the number
66//! of observed iterator items or the order in which operations are performed,
67//! and the compiler will generate bad code.
68//!
69//! And since most of these Iterator methods are documented to perform data
70//! reduction in a specific way, this problem cannot be solved by improving
71//! the standard library's `Iterator` implementation, at least not without
72//! breaking the API of `Iterator`, which would be Very Bad (tm) and is thus
73//! highly unlikely to happen.
74//!
75//! # What this crate provides
76//!
77//! [`IteratorILP`] is an Iterator extension trait that can be implemented for
78//! all iterators of known length, and provides variants of the standard
79//! reduction methods with a `STREAMS` const generic parameter. By tuning up
80//! this parameter, you divide the iterator reduction work across more and more
81//! instruction streams, exposing more and more instruction-level parallelism
82//! for the compiler and hardware to take advantage of.
83//!
84//! This is effectively
85//! [loop unrolling](https://en.wikipedia.org/wiki/Loop_unrolling), but instead
86//! of making your code unreadable by manually implementing the operation
87//! yourself, you let `IteratorILP` do it for you by just providing it with the
88//! tuning parameter it needs.
89//!
90//! So to reuse the above example...
91//!
92//! ```
93//! # let floats = [0.0; 8192];
94//! use iterator_ilp::IteratorILP;
95//! let sum = floats.iter().sum_ilp::<16, f32>();
96//! ```
97//!
98//! ...would sum a slice of floating-point numbers using 16 independent
99//! instruction streams, achieving a more respectable throughput of
100//! 17 billion floating-point sums per second on an Intel i9-10900 CPU running
101//! at 2.5 GHz. This corresponds to 6.8 additions per CPU cycle, which is
102//! reasonable when considering that the hardware can do 16 additions per second
103//! on correctly aligned SIMD data, but here the data is _not_ correctly
104//! aligned and hence reaching about half the hardware throughput is expected.
105//!
106//! # How many instruction streams do I need?
107//!
108//! The number of independent instruction streams you need to reach peak
109//! hardware performance depends on many factors:
110//!
111//! - What hardware you are running on
112//! - What hardware features (e.g. SIMD instruction set extensions) are used by
113//!   the compiled program
114//! - What type of data you are manipulating
115//! - How complex your input iterator and the reduction operation are
116//!
117//! Further, you cannot just tune the number of streams up indefinitely because
118//! managing more instruction streams requires more hardware resources (CPU
119//! registers, instruction cache...), and at some point you will run out of
120//! these scarce resources and your runtime performance will drop. Even before
121//! that, some internal compiler optimizer code complexity threshold may be
122//! reached at which point the compiler will decide to stop optimizing the code
123//! of individual instruction streams as much at it would optimize that of a
124//! normal reduction, which will reduce performance as well.
125//!
126//! To give orders of magnitude, simple reductions, like the floating point sum
127//! discussed above, can benefit from being spread over 16 instruction streams
128//! or more on some hardware (e.g. x86 CPUs with AVX enabled), while complex
129//! reductions (e.g. those using manually vectorized data) may not benefit from
130//! more than 2 streams, or could even already exhibit decreased performance in
131//! that configuration.
132//!
133//! Since the rules for determining the right number of streams are so complex,
134//! and involve information unknown to this crate, we leave it up to you to
135//! tune this parameter. An empirical approach is advised: take a workload
136//! whose performance you care about, benchmark it with various numbers of
137//! streams on a broad range of target configurations, and find out the right
138//! compromise for you (which may be a hardware-dependent compromise selected
139//! via `#[cfg()]` attributes and/or runtime detection if needed).
140
141#![cfg_attr(not(any(test, feature = "std")), no_std)]
142
143#[cfg(doc)]
144use core::iter::{Product, Sum};
145use core::{
146    cell::RefCell,
147    iter::FusedIterator,
148    ops::{Add, Mul},
149};
150use num_traits::{One, Zero};
151
152/// Iterator extension that provides instruction-parallel reductions
153///
154/// See the [crate-level documentation](crate) for more information on what
155/// instruction-level parallelism is, why it's needed, how much of it you need,
156/// and why standard iterator reductions may not provide enough of it.
157///
158/// This trait's documentation will instead focus on how and why ILP reduction
159/// semantics differ from standard reduction semantics.
160///
161/// # General strategy
162///
163/// All reductions provided by this trait use the name of the equivalent
164/// reduction operation provided by the standard [`Iterator`] trait, with an
165/// `_ilp` suffix that stands for Instruction-Level Parallelism and a `STREAMS`
166/// const parameter that lets you tune the number of independent instruction
167/// streams that you want to extract.
168///
169/// `STREAMS` must be at least one, but at the time of writing we cannot express
170/// this at the type level, so we handle requests for 0 streams through
171/// panicking instead.
172///
173/// ILP reductions are implemented by treating an [`Iterator`] as the
174/// interleaved output of `STREAMS` different iterators, that we will call
175/// streams in the following to avoid confusion:
176///
177/// - The first item is treated as if it were the first item of the first stream
178/// - The second item is treated as if it were the first item of the second stream
179/// - ...and so on until STREAMS items have been processed...
180/// - Then the (STREAMS+1)-th item is treated as if it were the second
181///   item of the first stream, and so on.
182///
183/// Each of these streams is independently processed using a close cousin of the
184/// algorithm that a standard iterator reduction would use, then at the end
185/// the results of individual reductions are merged into a global result.
186///
187/// Like all forms of parallelism, instruction-level parallelism does not
188/// handle early exit very well. To avoid losing its benefits, we must read out
189/// input data in groups of STREAMS elements, and only after that check if any
190/// of the elements that we have read requires us to terminate iteration.
191///
192/// In principle, a [`FusedIterator`] bound should be enough to satisfy this
193/// requirement. But in practice, good code generation could not be obtained
194/// without relying on the lower bound of [`Iterator::size_hint()`] to be
195/// correct for safety. This is a subset of the contract of [`TrustedLen`],
196/// which, unfortunately, is unstable.
197///
198/// Therefore, we provide our own [`TrustedLowerBound`] unsafe trait, which we
199/// implement for all standard library iterators. If you need to use
200/// `iterator_ilp` with another iterator whose lower size bound you trust, you
201/// can do either of the following:
202///
203/// - Implement [`TrustedLowerBound`] for this iterator, if it's a type that you
204///   control. This is the preferred path, because it allows users to leverage
205///   `iterator_ilp` without unsafe assertions about types outside of their
206///   control. In an ideal world, all numerical container libraries would
207///   eventually provide such implementations.
208/// - Use the [`AssertLowerBoundOk`] wrapper to unsafely assert, on your side,
209///   that **you** trust an iterator to have a `size_hint()` implementation that
210///   provides a correct lower bound.
211///
212/// That's it for the general strategy, now to get into the detail of particular
213/// algorithms, we must divide [`Iterator`] reductions into three categories:
214///
215/// - [Searches](#Searching) like [`Iterator::find()`] iterate until an item
216///   matching a user-provided predicate is found, then abort iteration.
217/// - [Accumulations](#Accumulating) like [`Iterator::fold()`] set up an
218///   accumulator and go through the entire input iterator, combining the
219///   accumulator with each item and returning the final accumulator at the end.
220/// - [`Iterator::sum()`] and [`Iterator::product()`] are technically
221///   accumulations, but their API is so different from that of other
222///   accumulations that they [are discussed separately](#sum-and-product).
223///
224/// # Searching
225///
226/// As mentioned earlier, data must be read in groups of `STREAMS` for optimal
227/// instruction level parallelism. As a result, the short-circuiting feature of
228/// Rust's standard search algorithms becomes somewhat meaningless and
229/// deceitful, so it was dropped and the iterator is consumed instead.
230///
231/// Users of iterators with side effects (e.g. [`inspect()`]) must bear in mind
232/// that when using the ILP version of search routines, elements may be read
233/// beyond the point where the search will terminate.
234///
235/// # Accumulating
236///
237/// The signature of [`fold_ilp()`] differs a fair bit from that of
238/// [`Iterator::fold()`] because instruction-parallel accumulation requires
239/// setting up `STREAMS` different accumulators at the beginning and merging
240/// them into one at the end. Users are invited to read [the documentation of
241/// `fold_ilp()`](IteratorILP::fold_ilp()) for more details about how its usage
242/// differs from that of standard [`fold()`].
243///
244/// Higher-level accumulation routines that do not expose the accumulator, like
245/// [`reduce_ilp()`], are not as drastically affected from an API standpoint.
246/// The main thing to keep in mind when using them is that since accumulation is
247/// performed in a different order, results will differ for non-associative
248/// reduction functions like floating-point summation, and the provided
249/// reduction callable will observe a different sequence of inputs, so it should
250/// not rely on ordering of inputs for correctness.
251///
252/// Although many numerical types implement `Add<&T>` in addition to `Add<T>`
253/// for user convenience, due to compiler limitations, better performance will
254/// often be achieved when iterating over numerical types by value, rather than
255/// by reference. If you have an iterator of references, you can usually achieve
256/// this by calling [`Iterator::copied()`].
257///
258/// # Sum and product
259///
260/// The definition of the [`Sum`] and [`Product`] traits is very high-level and
261/// does not allow us to inject the right code in the right place in order to
262/// achieve satisfactory code generation. Therefore, our versions of the
263/// [`sum()`] and [`product()`] iterator reductions have to use completely
264/// different trait bounds. For sane types, this is mostly transparent,
265/// reordering of operations aside.
266///
267/// [`fold()`]: Iterator::fold()
268/// [`fold_ilp()`]: IteratorILP::fold_ilp()
269/// [`inspect()`]: Iterator::inspect()
270/// [`product()`]: Iterator::product()
271/// [`product_ilp()`]: IteratorILP::product_ilp()
272/// [`reduce_ilp()`]: IteratorILP::reduce_ilp()
273/// [`sum()`]: Iterator::sum()
274/// [`sum_ilp()`]: IteratorILP::sum_ilp()
275/// [`TrustedLen`]: core::iter::TrustedLen
276pub trait IteratorILP: Iterator + Sized + TrustedLowerBound {
277    // === Searching ===
278
279    /// Like [`Iterator::any()`], but with multiple ILP streams and consumes the
280    /// iterator
281    ///
282    /// See also the [general IteratorILP documentation](IteratorILP) and [its
283    /// section on search routines](#Searching) in particular.
284    ///
285    /// # Panics
286    ///
287    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
288    ///   make progress.
289    #[inline]
290    fn any_ilp<const STREAMS: usize>(self, mut predicate: impl FnMut(Self::Item) -> bool) -> bool {
291        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
292        self.find_map_ilp::<STREAMS, _>(|item| predicate(item).then_some(true))
293            .unwrap_or(false)
294    }
295
296    /// Like [`Iterator::all()`], but with multiple ILP streams and consumes the iterator
297    ///
298    /// See also the [general IteratorILP documentation](IteratorILP) and [its
299    /// section on search routines](#Searching) in particular.
300    ///
301    /// # Panics
302    ///
303    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
304    ///   make progress.
305    #[inline]
306    fn all_ilp<const STREAMS: usize>(self, mut predicate: impl FnMut(Self::Item) -> bool) -> bool {
307        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
308        self.find_map_ilp::<STREAMS, _>(|item| (!predicate(item)).then_some(false))
309            .unwrap_or(true)
310    }
311
312    /// Like [`Iterator::find()`], but with multiple ILP streams and consumes the iterator
313    ///
314    /// See also the [general IteratorILP documentation](IteratorILP) and [its
315    /// section on search routines](#Searching) in particular.
316    ///
317    /// # Panics
318    ///
319    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
320    ///   make progress.
321    #[inline]
322    fn find_ilp<const STREAMS: usize>(
323        self,
324        mut predicate: impl FnMut(&Self::Item) -> bool,
325    ) -> Option<Self::Item> {
326        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
327
328        // Map the iterator in such a way that it returns Some(item) if the item
329        // matches the predicate
330        let mut iter = self.map(|item| predicate(&item).then_some(item));
331
332        // Process the regular part of the stream
333        let stream_len = iter.size_hint().0 / STREAMS;
334        for _ in 0..stream_len {
335            // Fetch one Option<Item> per stream
336            let item_opts: [Option<Self::Item>; STREAMS] =
337                // SAFETY: The TrustedLowerBound contract lets us assume than
338                //         the lower bound returned by size_hint is correct, and
339                //         the above loop will not iterate for more than this
340                //         amount of iteration, so this is trusted to be safe.
341                core::array::from_fn(|_| unsafe { iter.next().unwrap_unchecked() });
342
343            // Check if the item of interest was found
344            if let Some(item) = item_opts.into_iter().flatten().next() {
345                return Some(item);
346            }
347        }
348
349        // Process irregular elements at the end
350        iter.flatten().next()
351    }
352
353    /// Like [`Iterator::find_map()`], but with multiple ILP streams and consumes the iterator
354    ///
355    /// See also the [general IteratorILP documentation](IteratorILP) and [its
356    /// section on search routines](#Searching) in particular.
357    ///
358    /// # Panics
359    ///
360    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
361    ///   make progress.
362    #[inline]
363    fn find_map_ilp<const STREAMS: usize, Res>(
364        self,
365        f: impl FnMut(Self::Item) -> Option<Res>,
366    ) -> Option<Res> {
367        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
368        self.map(f)
369            .find_ilp::<STREAMS>(|res| res.is_some())
370            .flatten()
371    }
372
373    /// Like [`Iterator::position()`], but with multiple ILP streams and consumes the iterator
374    ///
375    /// See also the [general IteratorILP documentation](IteratorILP) and [its
376    /// section on search routines](#Searching) in particular.
377    ///
378    /// # Panics
379    ///
380    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
381    ///   make progress.
382    #[inline]
383    fn position_ilp<const STREAMS: usize>(
384        self,
385        mut predicate: impl FnMut(Self::Item) -> bool,
386    ) -> Option<usize> {
387        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
388        self.enumerate()
389            .find_map_ilp::<STREAMS, _>(|(idx, elem)| predicate(elem).then_some(idx))
390    }
391
392    /// Like [`Iterator::rposition()`], but with multiple ILP streams and consumes the iterator
393    ///
394    /// See also the [general IteratorILP documentation](IteratorILP) and [its
395    /// section on search routines](#Searching) in particular.
396    ///
397    /// # Panics
398    ///
399    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
400    ///   make progress.
401    #[inline]
402    fn rposition_ilp<const STREAMS: usize>(
403        self,
404        mut predicate: impl FnMut(Self::Item) -> bool,
405    ) -> Option<usize>
406    where
407        Self: DoubleEndedIterator + ExactSizeIterator,
408    {
409        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
410        self.enumerate()
411            .rev()
412            .find_map_ilp::<STREAMS, _>(|(idx, elem)| predicate(elem).then_some(idx))
413    }
414
415    // === Accumulating ===
416
417    /// Like [`Iterator::fold()`], but with multiple ILP streams and thus
418    /// multiple accumulators
419    ///
420    /// `neutral` should produce the neutral element of the computation being
421    /// performed. All accumulators will be initialized using this function,
422    /// and eventually merged using `merge`.
423    ///
424    /// Implementations of `accumulate` and `merge` should not be sensitive to
425    /// the traversal order of items and accumulators, respectively.
426    ///
427    /// See also the [general IteratorILP documentation](IteratorILP) and [its
428    /// section on accumulation](#Accumulating) in particular.
429    ///
430    /// # Panics
431    ///
432    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
433    ///   make progress.
434    #[inline]
435    fn fold_ilp<const STREAMS: usize, Acc>(
436        mut self,
437        mut neutral: impl FnMut() -> Acc,
438        mut accumulate: impl FnMut(Acc, Self::Item) -> Acc,
439        mut merge: impl FnMut(Acc, Acc) -> Acc,
440    ) -> Acc {
441        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
442
443        // Set up accumulators
444        let mut accumulators: [Option<Acc>; STREAMS] = core::array::from_fn(|_| Some(neutral()));
445        let mut accumulate_opt = |accumulator: &mut Option<Acc>, item| {
446            if let Some(prev_acc) = accumulator.take() {
447                *accumulator = Some(accumulate(prev_acc, item));
448            }
449        };
450
451        // Accumulate the regular part of the stream
452        let stream_len = self.size_hint().0 / STREAMS;
453        for _ in 0..stream_len {
454            for acc in &mut accumulators {
455                // SAFETY: The TrustedLowerBound contract lets us assume than
456                //         the lower bound returned by size_hint is correct, and
457                //         the above loop will not iterate for more than this
458                //         amount of iteration, so this is trusted to be safe.
459                accumulate_opt(acc, unsafe { self.next().unwrap_unchecked() });
460            }
461        }
462
463        // Merge the accumulators
464        let mut stride = if STREAMS.is_power_of_two() {
465            STREAMS
466        } else {
467            STREAMS.next_power_of_two()
468        };
469        while stride > 1 {
470            stride /= 2;
471            for i in 0..stride.min(STREAMS - stride) {
472                accumulators[i] = Some(merge(
473                    accumulators[i].take().unwrap(),
474                    accumulators[i + stride].take().unwrap(),
475                ));
476            }
477        }
478        let ilp_result = accumulators[0].take().unwrap();
479
480        // Accumulate remaining irregular elements using standard iterator fold,
481        // then merge (doing it like this improves floating-point accuracy)
482        merge(ilp_result, self.fold(neutral(), accumulate))
483    }
484
485    /// Like [`Iterator::reduce()`], but with multiple ILP streams
486    ///
487    /// Implementations of `reduce` should not be sensitive to the order in
488    /// which iterator items are traversed.
489    ///
490    /// See also the [general IteratorILP documentation](IteratorILP) and [its
491    /// section on accumulation](#Accumulating) in particular.
492    ///
493    /// # Panics
494    ///
495    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
496    ///   make progress.
497    #[inline]
498    fn reduce_ilp<const STREAMS: usize>(
499        self,
500        reduce: impl FnMut(Self::Item, Self::Item) -> Self::Item,
501    ) -> Option<Self::Item> {
502        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
503        let reduce = RefCell::new(reduce);
504        self.fold_ilp::<STREAMS, _>(
505            || None,
506            |acc_opt, item| {
507                Some(if let Some(acc) = acc_opt {
508                    reduce.borrow_mut()(acc, item)
509                } else {
510                    item
511                })
512            },
513            |acc_opt_1, acc_opt_2| match (acc_opt_1, acc_opt_2) {
514                (Some(a), Some(b)) => Some(reduce.borrow_mut()(a, b)),
515                (Some(a), _) | (_, Some(a)) => Some(a),
516                (None, None) => None,
517            },
518        )
519    }
520
521    // === Sum and product ===
522
523    /// Like [`Iterator::sum()`], but with multiple ILP streams, and uses
524    /// different trait bounds.
525    ///
526    /// See also the [general IteratorILP documentation](IteratorILP) and [its
527    /// section on sum and product](#sum-and-product) in particular.
528    ///
529    /// # Panics
530    ///
531    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
532    ///   make progress.
533    #[inline(always)]
534    fn sum_ilp<const STREAMS: usize, S: Add<Self::Item, Output = S> + Add<S> + Zero>(self) -> S {
535        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
536        self.fold_ilp::<STREAMS, _>(|| S::zero(), |acc, it| acc + it, |acc1, acc2| acc1 + acc2)
537    }
538
539    /// Like [`Iterator::product()`], but with multiple ILP streams, and uses
540    /// different trait bounds.
541    ///
542    /// See also the [general IteratorILP documentation](IteratorILP) and [its
543    /// section on sum and product](#sum-and-product) in particular.
544    ///
545    /// # Panics
546    ///
547    /// - If `STREAMS` is set to 0. Need at least one instruction stream to
548    ///   make progress.
549    #[inline]
550    fn product_ilp<const STREAMS: usize, P: Mul<Self::Item, Output = P> + Mul<P> + One>(self) -> P {
551        assert_ne!(STREAMS, 0, "Need at least one stream to make progress");
552        self.fold_ilp::<STREAMS, _>(|| P::one(), |acc, it| acc * it, |acc1, acc2| acc1 * acc2)
553    }
554}
555
556impl<I: Iterator + Sized + TrustedLowerBound> IteratorILP for I {}
557
558/// An iterator that reports an accurate lower bound using [`size_hint()`]
559///
560/// # Safety
561///
562/// The lower bound reported by this iterator is guaranteed to be accurate, in
563/// the sense that the iterator cannot output less items. Unsafe code can rely
564/// on this being correct for safety.
565///
566/// For optimal performance, the lower bound should also be exact (i.e. equal to
567/// the number of elements being returned) whenever possible, but this is not a
568/// safety-critical property.
569///
570/// Since this iterator trait is a subset of the unstable [`TrustedLen`]
571/// trait, it will be implemented for all implementations of [`TrustedLen`] as
572/// they stabilize.
573///
574/// [`size_hint()`]: Iterator::size_hint()
575/// [`TrustedLen`]: core::iter::TrustedLen
576pub unsafe trait TrustedLowerBound: Iterator {}
577//
578// SAFETY: All Iterator impls from std are trusted to be implemented correctly,
579//         since if you can't trust std, there is no hope for you...
580mod core_iters {
581    use crate::TrustedLowerBound;
582    use core::{
583        iter::{
584            Chain, Cloned, Copied, Cycle, Empty, Enumerate, Filter, FilterMap, FlatMap, Flatten,
585            FromFn, Fuse, Inspect, Map, MapWhile, Once, OnceWith, Peekable, Repeat, RepeatWith,
586            Rev, Scan, Skip, SkipWhile, StepBy, Successors, Take, TakeWhile, Zip,
587        },
588        ops::{Range, RangeFrom, RangeInclusive},
589        str::{CharIndices, Chars, EncodeUtf16, SplitAsciiWhitespace, SplitWhitespace},
590    };
591
592    unsafe impl<I> TrustedLowerBound for &mut I where I: TrustedLowerBound + ?Sized {}
593    unsafe impl<A, B> TrustedLowerBound for Chain<A, B>
594    where
595        A: TrustedLowerBound,
596        B: TrustedLowerBound<Item = <A as Iterator>::Item>,
597    {
598    }
599    unsafe impl TrustedLowerBound for CharIndices<'_> {}
600    unsafe impl TrustedLowerBound for Chars<'_> {}
601    unsafe impl<'a, I, T> TrustedLowerBound for Cloned<I>
602    where
603        I: TrustedLowerBound<Item = &'a T>,
604        T: 'a + Clone,
605    {
606    }
607    unsafe impl<'a, I, T> TrustedLowerBound for Copied<I>
608    where
609        I: TrustedLowerBound<Item = &'a T>,
610        T: 'a + Copy,
611    {
612    }
613    unsafe impl<I> TrustedLowerBound for Cycle<I> where I: TrustedLowerBound + Clone {}
614    unsafe impl<T> TrustedLowerBound for Empty<T> {}
615    unsafe impl TrustedLowerBound for EncodeUtf16<'_> {}
616    unsafe impl<I> TrustedLowerBound for Enumerate<I> where I: TrustedLowerBound {}
617    unsafe impl<I, P> TrustedLowerBound for Filter<I, P>
618    where
619        I: TrustedLowerBound,
620        P: FnMut(&<I as Iterator>::Item) -> bool,
621    {
622    }
623    unsafe impl<B, I, F> TrustedLowerBound for FilterMap<I, F>
624    where
625        F: FnMut(<I as Iterator>::Item) -> Option<B>,
626        I: TrustedLowerBound,
627    {
628    }
629    unsafe impl<I, U> TrustedLowerBound for Flatten<I>
630    where
631        I: TrustedLowerBound,
632        <I as Iterator>::Item: IntoIterator<IntoIter = U, Item = <U as Iterator>::Item>,
633        U: TrustedLowerBound,
634    {
635    }
636    unsafe impl<I, U, F> TrustedLowerBound for FlatMap<I, U, F>
637    where
638        I: TrustedLowerBound,
639        U: IntoIterator,
640        <U as IntoIterator>::IntoIter: TrustedLowerBound,
641        F: FnMut(<I as Iterator>::Item) -> U,
642    {
643    }
644    unsafe impl<T, F> TrustedLowerBound for FromFn<F> where F: FnMut() -> Option<T> {}
645    unsafe impl<I> TrustedLowerBound for Fuse<I> where I: TrustedLowerBound {}
646    unsafe impl<I, F> TrustedLowerBound for Inspect<I, F>
647    where
648        I: TrustedLowerBound,
649        F: FnMut(&<I as Iterator>::Item),
650    {
651    }
652    unsafe impl<B, I, F> TrustedLowerBound for Map<I, F>
653    where
654        F: FnMut(<I as Iterator>::Item) -> B,
655        I: TrustedLowerBound,
656    {
657    }
658    unsafe impl<B, I, F> TrustedLowerBound for MapWhile<I, F>
659    where
660        F: FnMut(<I as Iterator>::Item) -> Option<B>,
661        I: TrustedLowerBound,
662    {
663    }
664    unsafe impl<T> TrustedLowerBound for Once<T> {}
665    unsafe impl<A, F> TrustedLowerBound for OnceWith<F> where F: FnOnce() -> A {}
666    unsafe impl<I> TrustedLowerBound for Peekable<I> where I: TrustedLowerBound {}
667    unsafe impl TrustedLowerBound for Range<usize> {}
668    unsafe impl TrustedLowerBound for Range<isize> {}
669    unsafe impl TrustedLowerBound for Range<u8> {}
670    unsafe impl TrustedLowerBound for Range<i8> {}
671    unsafe impl TrustedLowerBound for Range<u16> {}
672    unsafe impl TrustedLowerBound for Range<i16> {}
673    unsafe impl TrustedLowerBound for Range<u32> {}
674    unsafe impl TrustedLowerBound for Range<i32> {}
675    unsafe impl TrustedLowerBound for Range<i64> {}
676    unsafe impl TrustedLowerBound for Range<u64> {}
677    unsafe impl TrustedLowerBound for RangeFrom<usize> {}
678    unsafe impl TrustedLowerBound for RangeFrom<isize> {}
679    unsafe impl TrustedLowerBound for RangeFrom<u8> {}
680    unsafe impl TrustedLowerBound for RangeFrom<i8> {}
681    unsafe impl TrustedLowerBound for RangeFrom<u16> {}
682    unsafe impl TrustedLowerBound for RangeFrom<i16> {}
683    unsafe impl TrustedLowerBound for RangeFrom<u32> {}
684    unsafe impl TrustedLowerBound for RangeFrom<i32> {}
685    unsafe impl TrustedLowerBound for RangeFrom<i64> {}
686    unsafe impl TrustedLowerBound for RangeFrom<u64> {}
687    unsafe impl TrustedLowerBound for RangeInclusive<usize> {}
688    unsafe impl TrustedLowerBound for RangeInclusive<isize> {}
689    unsafe impl TrustedLowerBound for RangeInclusive<u8> {}
690    unsafe impl TrustedLowerBound for RangeInclusive<i8> {}
691    unsafe impl TrustedLowerBound for RangeInclusive<u16> {}
692    unsafe impl TrustedLowerBound for RangeInclusive<i16> {}
693    unsafe impl TrustedLowerBound for RangeInclusive<u32> {}
694    unsafe impl TrustedLowerBound for RangeInclusive<i32> {}
695    unsafe impl TrustedLowerBound for RangeInclusive<i64> {}
696    unsafe impl TrustedLowerBound for RangeInclusive<u64> {}
697    unsafe impl<A: Clone> TrustedLowerBound for Repeat<A> {}
698    unsafe impl<A, F> TrustedLowerBound for RepeatWith<F> where F: FnMut() -> A {}
699    unsafe impl<I> TrustedLowerBound for Rev<I> where I: TrustedLowerBound + DoubleEndedIterator {}
700    unsafe impl<B, I, St, F> TrustedLowerBound for Scan<I, St, F>
701    where
702        F: FnMut(&mut St, <I as Iterator>::Item) -> Option<B>,
703        I: TrustedLowerBound,
704    {
705    }
706    unsafe impl<I> TrustedLowerBound for Skip<I> where I: TrustedLowerBound {}
707    unsafe impl<I, P> TrustedLowerBound for SkipWhile<I, P>
708    where
709        I: TrustedLowerBound,
710        P: FnMut(&<I as Iterator>::Item) -> bool,
711    {
712    }
713    unsafe impl TrustedLowerBound for SplitAsciiWhitespace<'_> {}
714    unsafe impl TrustedLowerBound for SplitWhitespace<'_> {}
715    unsafe impl<I> TrustedLowerBound for StepBy<I> where I: TrustedLowerBound {}
716    unsafe impl<T, F> TrustedLowerBound for Successors<T, F> where F: FnMut(&T) -> Option<T> {}
717    unsafe impl<I> TrustedLowerBound for Take<I> where I: TrustedLowerBound {}
718    unsafe impl<I, P> TrustedLowerBound for TakeWhile<I, P>
719    where
720        I: TrustedLowerBound,
721        P: FnMut(&<I as Iterator>::Item) -> bool,
722    {
723    }
724    unsafe impl<A, B> TrustedLowerBound for Zip<A, B>
725    where
726        A: TrustedLowerBound,
727        B: TrustedLowerBound,
728    {
729    }
730    unsafe impl<T, const N: usize> TrustedLowerBound for core::array::IntoIter<T, N> {}
731    unsafe impl TrustedLowerBound for core::ascii::EscapeDefault {}
732    unsafe impl<I> TrustedLowerBound for core::char::DecodeUtf16<I> where
733        I: TrustedLowerBound<Item = u16>
734    {
735    }
736    unsafe impl TrustedLowerBound for core::char::EscapeDebug {}
737    unsafe impl TrustedLowerBound for core::char::EscapeDefault {}
738    unsafe impl TrustedLowerBound for core::char::EscapeUnicode {}
739    unsafe impl TrustedLowerBound for core::char::ToLowercase {}
740    unsafe impl TrustedLowerBound for core::char::ToUppercase {}
741    unsafe impl<A> TrustedLowerBound for core::option::Iter<'_, A> {}
742    unsafe impl<A> TrustedLowerBound for core::option::IterMut<'_, A> {}
743    unsafe impl<A> TrustedLowerBound for core::option::IntoIter<A> {}
744    unsafe impl<A> TrustedLowerBound for core::result::Iter<'_, A> {}
745    unsafe impl<A> TrustedLowerBound for core::result::IterMut<'_, A> {}
746    unsafe impl<A> TrustedLowerBound for core::result::IntoIter<A> {}
747    unsafe impl<T> TrustedLowerBound for core::slice::Chunks<'_, T> {}
748    unsafe impl<T> TrustedLowerBound for core::slice::ChunksExact<'_, T> {}
749    unsafe impl<T> TrustedLowerBound for core::slice::ChunksExactMut<'_, T> {}
750    unsafe impl<T> TrustedLowerBound for core::slice::ChunksMut<'_, T> {}
751    unsafe impl TrustedLowerBound for core::slice::EscapeAscii<'_> {}
752    unsafe impl<T> TrustedLowerBound for core::slice::Iter<'_, T> {}
753    unsafe impl<T> TrustedLowerBound for core::slice::IterMut<'_, T> {}
754    unsafe impl<T> TrustedLowerBound for core::slice::RChunks<'_, T> {}
755    unsafe impl<T> TrustedLowerBound for core::slice::RChunksExact<'_, T> {}
756    unsafe impl<T> TrustedLowerBound for core::slice::RChunksExactMut<'_, T> {}
757    unsafe impl<T> TrustedLowerBound for core::slice::RChunksMut<'_, T> {}
758    unsafe impl<T, P> TrustedLowerBound for core::slice::RSplit<'_, T, P> where P: FnMut(&T) -> bool {}
759    unsafe impl<T, P> TrustedLowerBound for core::slice::RSplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
760    unsafe impl<T, P> TrustedLowerBound for core::slice::RSplitN<'_, T, P> where P: FnMut(&T) -> bool {}
761    unsafe impl<T, P> TrustedLowerBound for core::slice::RSplitNMut<'_, T, P> where P: FnMut(&T) -> bool {}
762    unsafe impl<T, P> TrustedLowerBound for core::slice::Split<'_, T, P> where P: FnMut(&T) -> bool {}
763    unsafe impl<T, P> TrustedLowerBound for core::slice::SplitInclusive<'_, T, P> where
764        P: FnMut(&T) -> bool
765    {
766    }
767    unsafe impl<T, P> TrustedLowerBound for core::slice::SplitInclusiveMut<'_, T, P> where
768        P: FnMut(&T) -> bool
769    {
770    }
771    unsafe impl<T, P> TrustedLowerBound for core::slice::SplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
772    unsafe impl<T, P> TrustedLowerBound for core::slice::SplitN<'_, T, P> where P: FnMut(&T) -> bool {}
773    unsafe impl<T, P> TrustedLowerBound for core::slice::SplitNMut<'_, T, P> where P: FnMut(&T) -> bool {}
774    unsafe impl<T> TrustedLowerBound for core::slice::Windows<'_, T> {}
775    unsafe impl TrustedLowerBound for core::str::Bytes<'_> {}
776    unsafe impl TrustedLowerBound for core::str::EscapeDebug<'_> {}
777    unsafe impl TrustedLowerBound for core::str::EscapeDefault<'_> {}
778    unsafe impl TrustedLowerBound for core::str::EscapeUnicode<'_> {}
779    unsafe impl TrustedLowerBound for core::str::Lines<'_> {}
780
781    #[cfg(feature = "std")]
782    mod std {
783        use crate::TrustedLowerBound;
784        use core::hash::{BuildHasher, Hash};
785        use std::{
786            env::{Args, ArgsOs, SplitPaths, Vars, VarsOs},
787            fs::ReadDir,
788            io::{BufRead, Read},
789            path::{Ancestors, Components},
790            process::{CommandArgs, CommandEnvs},
791            sync::mpsc::TryIter,
792            vec::Splice,
793        };
794
795        unsafe impl TrustedLowerBound for Ancestors<'_> {}
796        unsafe impl TrustedLowerBound for Args {}
797        unsafe impl TrustedLowerBound for ArgsOs {}
798        unsafe impl<I> TrustedLowerBound for Box<I> where I: TrustedLowerBound {}
799        unsafe impl TrustedLowerBound for CommandArgs<'_> {}
800        unsafe impl TrustedLowerBound for CommandEnvs<'_> {}
801        unsafe impl TrustedLowerBound for Components<'_> {}
802        unsafe impl TrustedLowerBound for ReadDir {}
803        unsafe impl<I> TrustedLowerBound for Splice<'_, I> where I: TrustedLowerBound {}
804        unsafe impl TrustedLowerBound for SplitPaths<'_> {}
805        unsafe impl<T> TrustedLowerBound for TryIter<'_, T> {}
806        unsafe impl TrustedLowerBound for Vars {}
807        unsafe impl TrustedLowerBound for VarsOs {}
808        unsafe impl<T> TrustedLowerBound for std::collections::binary_heap::Drain<'_, T> {}
809        unsafe impl<T> TrustedLowerBound for std::collections::binary_heap::Iter<'_, T> {}
810        unsafe impl<T> TrustedLowerBound for std::collections::binary_heap::IntoIter<T> {}
811        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::IntoIter<K, V> {}
812        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::IntoKeys<K, V> {}
813        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::IntoValues<K, V> {}
814        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::Iter<'_, K, V> {}
815        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::IterMut<'_, K, V> {}
816        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::Keys<'_, K, V> {}
817        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::Range<'_, K, V> {}
818        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::RangeMut<'_, K, V> {}
819        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::Values<'_, K, V> {}
820        unsafe impl<K, V> TrustedLowerBound for std::collections::btree_map::ValuesMut<'_, K, V> {}
821        unsafe impl<T> TrustedLowerBound for std::collections::btree_set::IntoIter<T> {}
822        unsafe impl<T> TrustedLowerBound for std::collections::btree_set::Iter<'_, T> {}
823        unsafe impl<T> TrustedLowerBound for std::collections::btree_set::Range<'_, T> {}
824        unsafe impl<T: Ord> TrustedLowerBound for std::collections::btree_set::SymmetricDifference<'_, T> {}
825        unsafe impl<T: Ord> TrustedLowerBound for std::collections::btree_set::Union<'_, T> {}
826        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::Drain<'_, K, V> {}
827        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::IntoIter<K, V> {}
828        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::IntoKeys<K, V> {}
829        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::IntoValues<K, V> {}
830        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::Iter<'_, K, V> {}
831        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::IterMut<'_, K, V> {}
832        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::Keys<'_, K, V> {}
833        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::Values<'_, K, V> {}
834        unsafe impl<K, V> TrustedLowerBound for std::collections::hash_map::ValuesMut<'_, K, V> {}
835        unsafe impl<T, S> TrustedLowerBound for std::collections::hash_set::Difference<'_, T, S>
836        where
837            T: Eq + Hash,
838            S: BuildHasher,
839        {
840        }
841        unsafe impl<T, S> TrustedLowerBound for std::collections::hash_set::Intersection<'_, T, S>
842        where
843            T: Eq + Hash,
844            S: BuildHasher,
845        {
846        }
847        unsafe impl<T, S> TrustedLowerBound for std::collections::hash_set::SymmetricDifference<'_, T, S>
848        where
849            T: Eq + Hash,
850            S: BuildHasher,
851        {
852        }
853        unsafe impl<T, S> TrustedLowerBound for std::collections::hash_set::Union<'_, T, S>
854        where
855            T: Eq + Hash,
856            S: BuildHasher,
857        {
858        }
859        unsafe impl<K> TrustedLowerBound for std::collections::hash_set::Drain<'_, K> {}
860        unsafe impl<K> TrustedLowerBound for std::collections::hash_set::IntoIter<K> {}
861        unsafe impl<K> TrustedLowerBound for std::collections::hash_set::Iter<'_, K> {}
862        unsafe impl<T> TrustedLowerBound for std::collections::linked_list::IntoIter<T> {}
863        unsafe impl<T> TrustedLowerBound for std::collections::linked_list::Iter<'_, T> {}
864        unsafe impl<T> TrustedLowerBound for std::collections::linked_list::IterMut<'_, T> {}
865        unsafe impl<T> TrustedLowerBound for std::collections::vec_deque::Drain<'_, T> {}
866        unsafe impl<T> TrustedLowerBound for std::collections::vec_deque::IntoIter<T> {}
867        unsafe impl<T> TrustedLowerBound for std::collections::vec_deque::Iter<'_, T> {}
868        unsafe impl<T> TrustedLowerBound for std::collections::vec_deque::IterMut<'_, T> {}
869        unsafe impl<R: Read> TrustedLowerBound for std::io::Bytes<R> {}
870        unsafe impl<B: BufRead> TrustedLowerBound for std::io::Lines<B> {}
871        unsafe impl<B: BufRead> TrustedLowerBound for std::io::Split<B> {}
872        unsafe impl TrustedLowerBound for std::string::Drain<'_> {}
873        unsafe impl TrustedLowerBound for std::net::Incoming<'_> {}
874        unsafe impl TrustedLowerBound for std::path::Iter<'_> {}
875        unsafe impl<T> TrustedLowerBound for std::sync::mpsc::IntoIter<T> {}
876        unsafe impl<T> TrustedLowerBound for std::sync::mpsc::Iter<'_, T> {}
877        unsafe impl<T> TrustedLowerBound for std::vec::Drain<'_, T> {}
878        unsafe impl<T> TrustedLowerBound for std::vec::IntoIter<T> {}
879
880        #[cfg(target_os = "windows")]
881        mod windows {
882            use crate::TrustedLowerBound;
883            use std::os::windows::ffi::EncodeWide;
884
885            unsafe impl TrustedLowerBound for EncodeWide<'_> {}
886        }
887    }
888}
889
890/// Manual implementation of [`TrustedLowerBound`] for an iterator
891#[derive(Copy, Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
892pub struct AssertLowerBoundOk<I: Iterator>(I);
893//
894impl<I: Iterator> AssertLowerBoundOk<I> {
895    /// Assert that the lower size bound provided by an iterator's `size_hint()`
896    /// method is correct.
897    ///
898    /// # Safety
899    ///
900    /// The lower size bound must indeed be correct.
901    #[inline]
902    pub unsafe fn new(inner: I) -> Self {
903        Self(inner)
904    }
905}
906//
907impl<I: DoubleEndedIterator> DoubleEndedIterator for AssertLowerBoundOk<I> {
908    #[inline]
909    fn next_back(&mut self) -> Option<Self::Item> {
910        self.0.next_back()
911    }
912
913    #[inline]
914    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
915        self.0.nth_back(n)
916    }
917}
918//
919impl<I: ExactSizeIterator> ExactSizeIterator for AssertLowerBoundOk<I> {
920    #[inline]
921    fn len(&self) -> usize {
922        self.0.len()
923    }
924}
925//
926impl<I: FusedIterator> FusedIterator for AssertLowerBoundOk<I> {}
927//
928impl<I: Iterator> Iterator for AssertLowerBoundOk<I> {
929    type Item = I::Item;
930
931    #[inline]
932    fn next(&mut self) -> Option<Self::Item> {
933        self.0.next()
934    }
935
936    #[inline]
937    fn size_hint(&self) -> (usize, Option<usize>) {
938        self.0.size_hint()
939    }
940
941    #[inline]
942    fn count(self) -> usize
943    where
944        I: Sized,
945    {
946        self.0.count()
947    }
948
949    #[inline]
950    fn last(self) -> Option<Self::Item>
951    where
952        I: Sized,
953    {
954        self.0.last()
955    }
956
957    #[inline]
958    fn nth(&mut self, n: usize) -> Option<Self::Item> {
959        self.0.nth(n)
960    }
961}
962//
963// # Safety
964//
965// Safety assertion is offloaded to the `new()` constructor
966unsafe impl<I: Iterator> TrustedLowerBound for AssertLowerBoundOk<I> {}
967
968#[cfg(test)]
969mod tests {
970    use super::*;
971    use proptest::prelude::*;
972    use static_assertions::assert_impl_all;
973
974    assert_impl_all!(
975        std::slice::Iter<'static, u32>: FusedIterator, TrustedLowerBound
976    );
977
978    proptest! {
979        #[test]
980        fn assert_lower_bound_basic(data: Vec<u8>) {
981            let raw = data.iter();
982            // SAFETY: The size_hint of Vec's iterator is trusted
983            let iter = unsafe { AssertLowerBoundOk::new(raw.clone()) };
984            assert_eq!(iter.size_hint(), raw.size_hint());
985            assert_eq!(iter.len(), raw.len());
986            assert_eq!(iter.clone().count(), raw.clone().count());
987            assert_eq!(iter.clone().next(), raw.clone().next());
988            assert_eq!(iter.clone().next_back(), raw.clone().next_back());
989            assert_eq!(iter.clone().last(), raw.clone().last());
990        }
991
992        #[test]
993        fn assert_lower_bound_strided(data: Vec<u8>, stride: usize) {
994            let raw = data.iter();
995            // SAFETY: The size_hint of Vec's iterator is trusted
996            let iter = unsafe { AssertLowerBoundOk::new(raw.clone()) };
997            assert_eq!(iter.clone().nth(stride), raw.clone().nth(stride));
998            assert_eq!(iter.clone().nth_back(stride), raw.clone().nth_back(stride));
999        }
1000
1001        #[test]
1002        fn any(dataset: Vec<u8>, needle: u8) {
1003            let predicate = |&item| item == needle;
1004            let expected = dataset.iter().any(predicate);
1005            prop_assert_eq!(dataset.iter().any_ilp::<1>(predicate), expected);
1006            prop_assert_eq!(dataset.iter().any_ilp::<2>(predicate), expected);
1007            prop_assert_eq!(dataset.iter().any_ilp::<3>(predicate), expected);
1008            prop_assert_eq!(dataset.iter().any_ilp::<4>(predicate), expected);
1009            prop_assert_eq!(dataset.iter().any_ilp::<5>(predicate), expected);
1010            prop_assert_eq!(dataset.iter().any_ilp::<6>(predicate), expected);
1011        }
1012
1013        #[test]
1014        fn all(dataset: Vec<u8>, needle: u8) {
1015            let predicate = |&item| item == needle;
1016            let expected = dataset.iter().all(predicate);
1017            prop_assert_eq!(dataset.iter().all_ilp::<1>(predicate), expected);
1018            prop_assert_eq!(dataset.iter().all_ilp::<2>(predicate), expected);
1019            prop_assert_eq!(dataset.iter().all_ilp::<3>(predicate), expected);
1020            prop_assert_eq!(dataset.iter().all_ilp::<4>(predicate), expected);
1021            prop_assert_eq!(dataset.iter().all_ilp::<5>(predicate), expected);
1022            prop_assert_eq!(dataset.iter().all_ilp::<6>(predicate), expected);
1023        }
1024
1025        #[test]
1026        fn find(dataset: Vec<u8>, needle: u8) {
1027            let predicate = |item: &&u8| **item == needle;
1028            let expected = dataset.iter().find(predicate);
1029            prop_assert_eq!(dataset.iter().find_ilp::<1>(predicate), expected);
1030            prop_assert_eq!(dataset.iter().find_ilp::<2>(predicate), expected);
1031            prop_assert_eq!(dataset.iter().find_ilp::<3>(predicate), expected);
1032            prop_assert_eq!(dataset.iter().find_ilp::<4>(predicate), expected);
1033            prop_assert_eq!(dataset.iter().find_ilp::<5>(predicate), expected);
1034            prop_assert_eq!(dataset.iter().find_ilp::<6>(predicate), expected);
1035        }
1036
1037        #[test]
1038        fn find_map(dataset: Vec<u8>, needle: u8) {
1039            let find_map = |item: &u8| (*item == needle).then_some(42);
1040            let expected = dataset.iter().find_map(find_map);
1041            prop_assert_eq!(dataset.iter().find_map_ilp::<1, _>(find_map), expected);
1042            prop_assert_eq!(dataset.iter().find_map_ilp::<2, _>(find_map), expected);
1043            prop_assert_eq!(dataset.iter().find_map_ilp::<3, _>(find_map), expected);
1044            prop_assert_eq!(dataset.iter().find_map_ilp::<4, _>(find_map), expected);
1045            prop_assert_eq!(dataset.iter().find_map_ilp::<5, _>(find_map), expected);
1046            prop_assert_eq!(dataset.iter().find_map_ilp::<6, _>(find_map), expected);
1047        }
1048
1049        #[test]
1050        fn position(dataset: Vec<u8>, needle: u8) {
1051            let predicate = |item: &u8| *item == needle;
1052            let expected = dataset.iter().position(predicate);
1053            prop_assert_eq!(dataset.iter().position_ilp::<1>(predicate), expected);
1054            prop_assert_eq!(dataset.iter().position_ilp::<2>(predicate), expected);
1055            prop_assert_eq!(dataset.iter().position_ilp::<3>(predicate), expected);
1056            prop_assert_eq!(dataset.iter().position_ilp::<4>(predicate), expected);
1057            prop_assert_eq!(dataset.iter().position_ilp::<5>(predicate), expected);
1058            prop_assert_eq!(dataset.iter().position_ilp::<6>(predicate), expected);
1059        }
1060
1061        #[test]
1062        fn rposition(dataset: Vec<u8>, needle: u8) {
1063            let predicate = |item: &u8| *item == needle;
1064            let expected = dataset.iter().rposition(predicate);
1065            prop_assert_eq!(dataset.iter().rposition_ilp::<1>(predicate), expected);
1066            prop_assert_eq!(dataset.iter().rposition_ilp::<2>(predicate), expected);
1067            prop_assert_eq!(dataset.iter().rposition_ilp::<3>(predicate), expected);
1068            prop_assert_eq!(dataset.iter().rposition_ilp::<4>(predicate), expected);
1069            prop_assert_eq!(dataset.iter().rposition_ilp::<5>(predicate), expected);
1070            prop_assert_eq!(dataset.iter().rposition_ilp::<6>(predicate), expected);
1071        }
1072
1073        #[test]
1074        fn fold(dataset: Vec<u8>) {
1075            let zero = || 0;
1076            let accumulate = |a, &b| a + b as u64;
1077            let merge = |a, b| a + b;
1078            let expected = dataset.iter().fold(zero(), accumulate);
1079            prop_assert_eq!(
1080                dataset.iter().fold_ilp::<1, _>(zero, accumulate, merge),
1081                expected
1082            );
1083            prop_assert_eq!(
1084                dataset.iter().fold_ilp::<2, _>(zero, accumulate, merge),
1085                expected
1086            );
1087            prop_assert_eq!(
1088                dataset.iter().fold_ilp::<3, _>(zero, accumulate, merge),
1089                expected
1090            );
1091            prop_assert_eq!(
1092                dataset.iter().fold_ilp::<4, _>(zero, accumulate, merge),
1093                expected
1094            );
1095            prop_assert_eq!(
1096                dataset.iter().fold_ilp::<5, _>(zero, accumulate, merge),
1097                expected
1098            );
1099            prop_assert_eq!(
1100                dataset.iter().fold_ilp::<6, _>(zero, accumulate, merge),
1101                expected
1102            );
1103        }
1104
1105        #[test]
1106        fn reduce(dataset: Vec<u64>) {
1107            let reduce = |a: u64, b| a.wrapping_add(b);
1108            let expected = dataset.iter().copied().reduce(reduce);
1109            prop_assert_eq!(dataset.iter().copied().reduce_ilp::<1>(reduce), expected);
1110            prop_assert_eq!(dataset.iter().copied().reduce_ilp::<2>(reduce), expected);
1111            prop_assert_eq!(dataset.iter().copied().reduce_ilp::<3>(reduce), expected);
1112            prop_assert_eq!(dataset.iter().copied().reduce_ilp::<4>(reduce), expected);
1113            prop_assert_eq!(dataset.iter().copied().reduce_ilp::<5>(reduce), expected);
1114            prop_assert_eq!(dataset.iter().copied().reduce_ilp::<6>(reduce), expected);
1115        }
1116
1117        #[test]
1118        fn sum(dataset: Vec<u8>) {
1119            let dataset = dataset.into_iter().map(|i| i as u64).collect::<Vec<_>>();
1120            let expected = dataset.iter().copied().sum::<u64>();
1121            prop_assert_eq!(dataset.iter().copied().sum_ilp::<1, u64>(), expected);
1122            prop_assert_eq!(dataset.iter().copied().sum_ilp::<2, u64>(), expected);
1123            prop_assert_eq!(dataset.iter().copied().sum_ilp::<3, u64>(), expected);
1124            prop_assert_eq!(dataset.iter().copied().sum_ilp::<4, u64>(), expected);
1125            prop_assert_eq!(dataset.iter().copied().sum_ilp::<5, u64>(), expected);
1126            prop_assert_eq!(dataset.iter().copied().sum_ilp::<6, u64>(), expected);
1127        }
1128
1129        #[test]
1130        fn product(dataset: Vec<u8>) {
1131            let dataset = dataset
1132                .into_iter()
1133                .map(|i| (i as f64 / 256.0) + 0.5)
1134                .collect::<Vec<_>>();
1135            let expected = dataset.iter().copied().product::<f64>();
1136            let assert_close = |result: f64| {
1137                prop_assert!((result - expected).abs() < 1e-6 * expected.abs());
1138                Ok(())
1139            };
1140            assert_close(dataset.iter().copied().product_ilp::<1, f64>())?;
1141            assert_close(dataset.iter().copied().product_ilp::<2, f64>())?;
1142            assert_close(dataset.iter().copied().product_ilp::<3, f64>())?;
1143            assert_close(dataset.iter().copied().product_ilp::<4, f64>())?;
1144            assert_close(dataset.iter().copied().product_ilp::<5, f64>())?;
1145            assert_close(dataset.iter().copied().product_ilp::<6, f64>())?;
1146        }
1147    }
1148}
iterator_ilp/lib.rs

iterator_ilp/
lib.rs
