1 //! Parallel iterator types for [ranges][std::range],
2 //! the type for values created by `a..b` expressions
4 //! You will rarely need to interact with this module directly unless you have
5 //! need to name one of the iterator types.
8 //! use rayon::prelude::*;
10 //! let r = (0..100u64).into_par_iter()
13 //! // compare result with sequential calculation
14 //! assert_eq!((0..100).sum::<u64>(), r);
17 //! [std::range]: https://doc.rust-lang.org/core/ops/struct.Range.html
19 use crate::iter
::plumbing
::*;
22 use std
::convert
::TryFrom
;
26 /// Parallel iterator over a range, implemented for all integer types and `char`.
28 /// **Note:** The `zip` operation requires `IndexedParallelIterator`
29 /// which is not implemented for `u64`, `i64`, `u128`, or `i128`.
32 /// use rayon::prelude::*;
34 /// let p = (0..25usize).into_par_iter()
36 /// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
37 /// .map(|(x, y)| x * y)
40 /// let s = (0..25usize).zip(0..25)
41 /// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
42 /// .map(|(x, y)| x * y)
47 #[derive(Debug, Clone)]
52 /// Implemented for ranges of all primitive integer types and `char`.
53 impl<T
> IntoParallelIterator
for Range
<T
>
55 Iter
<T
>: ParallelIterator
,
57 type Item
= <Iter
<T
> as ParallelIterator
>::Item
;
60 fn into_par_iter(self) -> Self::Iter
{
65 struct IterProducer
<T
> {
69 impl<T
> IntoIterator
for IterProducer
<T
>
73 type Item
= <Range
<T
> as Iterator
>::Item
;
74 type IntoIter
= Range
<T
>;
76 fn into_iter(self) -> Self::IntoIter
{
81 /// These traits help drive integer type inference. Without them, an unknown `{integer}` type only
82 /// has constraints on `Iter<{integer}>`, which will probably give up and use `i32`. By adding
83 /// these traits on the item type, the compiler can see a more direct constraint to infer like
84 /// `{integer}: RangeInteger`, which works better. See `test_issue_833` for an example.
86 /// They have to be `pub` since they're seen in the public `impl ParallelIterator` constraints, but
87 /// we put them in a private modules so they're not actually reachable in our public API.
91 /// Implementation details of `ParallelIterator for Iter<Self>`
92 pub trait RangeInteger
: Sized
+ Send
{
95 fn drive_unindexed
<C
>(iter
: Iter
<Self>, consumer
: C
) -> C
::Result
97 C
: UnindexedConsumer
<Self>;
99 fn opt_len(iter
: &Iter
<Self>) -> Option
<usize>;
102 /// Implementation details of `IndexedParallelIterator for Iter<Self>`
103 pub trait IndexedRangeInteger
: RangeInteger
{
106 fn drive
<C
>(iter
: Iter
<Self>, consumer
: C
) -> C
::Result
110 fn len(iter
: &Iter
<Self>) -> usize;
112 fn with_producer
<CB
>(iter
: Iter
<Self>, callback
: CB
) -> CB
::Output
114 CB
: ProducerCallback
<Self>;
117 use private
::{IndexedRangeInteger, RangeInteger}
;
119 impl<T
: RangeInteger
> ParallelIterator
for Iter
<T
> {
122 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
124 C
: UnindexedConsumer
<T
>,
126 T
::drive_unindexed(self, consumer
)
130 fn opt_len(&self) -> Option
<usize> {
135 impl<T
: IndexedRangeInteger
> IndexedParallelIterator
for Iter
<T
> {
136 fn drive
<C
>(self, consumer
: C
) -> C
::Result
140 T
::drive(self, consumer
)
144 fn len(&self) -> usize {
148 fn with_producer
<CB
>(self, callback
: CB
) -> CB
::Output
150 CB
: ProducerCallback
<T
>,
152 T
::with_producer(self, callback
)
156 macro_rules
! indexed_range_impl
{
158 impl RangeInteger
for $t
{
161 fn drive_unindexed
<C
>(iter
: Iter
<$t
>, consumer
: C
) -> C
::Result
163 C
: UnindexedConsumer
<$t
>,
165 bridge(iter
, consumer
)
168 fn opt_len(iter
: &Iter
<$t
>) -> Option
<usize> {
169 Some(iter
.range
.len())
173 impl IndexedRangeInteger
for $t
{
176 fn drive
<C
>(iter
: Iter
<$t
>, consumer
: C
) -> C
::Result
180 bridge(iter
, consumer
)
183 fn len(iter
: &Iter
<$t
>) -> usize {
187 fn with_producer
<CB
>(iter
: Iter
<$t
>, callback
: CB
) -> CB
::Output
189 CB
: ProducerCallback
<$t
>,
191 callback
.callback(IterProducer { range: iter.range }
)
195 impl Producer
for IterProducer
<$t
> {
196 type Item
= <Range
<$t
> as Iterator
>::Item
;
197 type IntoIter
= Range
<$t
>;
198 fn into_iter(self) -> Self::IntoIter
{
202 fn split_at(self, index
: usize) -> (Self, Self) {
203 assert
!(index
<= self.range
.len());
204 // For signed $t, the length and requested index could be greater than $t::MAX, and
205 // then `index as $t` could wrap to negative, so wrapping_add is necessary.
206 let mid
= self.range
.start
.wrapping_add(index
as $t
);
207 let left
= self.range
.start
..mid
;
208 let right
= mid
..self.range
.end
;
209 (IterProducer { range: left }
, IterProducer { range: right }
)
215 trait UnindexedRangeLen
<L
> {
219 macro_rules
! unindexed_range_impl
{
220 ( $t
:ty
, $len_t
:ty
) => {
221 impl UnindexedRangeLen
<$len_t
> for Range
<$t
> {
222 fn len(&self) -> $len_t
{
223 let &Range { start, end }
= self;
225 end
.wrapping_sub(start
) as $len_t
232 impl RangeInteger
for $t
{
235 fn drive_unindexed
<C
>(iter
: Iter
<$t
>, consumer
: C
) -> C
::Result
237 C
: UnindexedConsumer
<$t
>,
240 fn offset(start
: $t
) -> impl Fn(usize) -> $t
{
241 move |i
| start
.wrapping_add(i
as $t
)
244 if let Some(len
) = iter
.opt_len() {
245 // Drive this in indexed mode for better `collect`.
248 .map(offset(iter
.range
.start
))
251 bridge_unindexed(IterProducer { range: iter.range }
, consumer
)
255 fn opt_len(iter
: &Iter
<$t
>) -> Option
<usize> {
256 usize::try_from(iter
.range
.len()).ok()
260 impl UnindexedProducer
for IterProducer
<$t
> {
263 fn split(mut self) -> (Self, Option
<Self>) {
264 let index
= self.range
.len() / 2;
266 let mid
= self.range
.start
.wrapping_add(index
as $t
);
267 let right
= mid
..self.range
.end
;
268 self.range
.end
= mid
;
269 (self, Some(IterProducer { range: right }
))
275 fn fold_with
<F
>(self, folder
: F
) -> F
277 F
: Folder
<Self::Item
>,
279 folder
.consume_iter(self)
285 // all Range<T> with ExactSizeIterator
286 indexed_range_impl
! {u8}
287 indexed_range_impl
! {u16}
288 indexed_range_impl
! {u32}
289 indexed_range_impl
! {usize}
290 indexed_range_impl
! {i8}
291 indexed_range_impl
! {i16}
292 indexed_range_impl
! {i32}
293 indexed_range_impl
! {isize}
295 // other Range<T> with just Iterator
296 unindexed_range_impl
! {u64, u64}
297 unindexed_range_impl
! {i64, u64}
298 unindexed_range_impl
! {u128, u128}
299 unindexed_range_impl
! {i128, u128}
301 // char is special because of the surrogate range hole
302 macro_rules
! convert_char
{
303 ( $
self:ident
. $method
:ident ( $
( $arg
:expr
),* ) ) => {{
304 let start
= $
self.range
.start
as u32;
305 let end
= $
self.range
.end
as u32;
306 if start
< 0xD800 && 0xE000 < end
{
307 // chain the before and after surrogate range fragments
311 .map(|codepoint
| unsafe { char::from_u32_unchecked(codepoint) }
)
312 .$
method($
( $arg
),*)
314 // no surrogate range to worry about
317 .map(|codepoint
| unsafe { char::from_u32_unchecked(codepoint) }
)
318 .$
method($
( $arg
),*)
323 impl ParallelIterator
for Iter
<char> {
326 fn drive_unindexed
<C
>(self, consumer
: C
) -> C
::Result
328 C
: UnindexedConsumer
<Self::Item
>,
330 convert_char
!(self.drive(consumer
))
333 fn opt_len(&self) -> Option
<usize> {
338 impl IndexedParallelIterator
for Iter
<char> {
339 // Split at the surrogate range first if we're allowed to
340 fn drive
<C
>(self, consumer
: C
) -> C
::Result
342 C
: Consumer
<Self::Item
>,
344 convert_char
!(self.drive(consumer
))
347 fn len(&self) -> usize {
348 // Taken from <char as Step>::steps_between
349 let start
= self.range
.start
as u32;
350 let end
= self.range
.end
as u32;
352 let mut count
= end
- start
;
353 if start
< 0xD800 && 0xE000 <= end
{
362 fn with_producer
<CB
>(self, callback
: CB
) -> CB
::Output
364 CB
: ProducerCallback
<Self::Item
>,
366 convert_char
!(self.with_producer(callback
))
371 fn check_range_split_at_overflow() {
372 // Note, this split index overflows i8!
373 let producer
= IterProducer { range: -100i8..100 }
;
374 let (left
, right
) = producer
.split_at(150);
375 let r1
: i32 = left
.range
.map(i32::from
).sum();
376 let r2
: i32 = right
.range
.map(i32::from
).sum();
377 assert_eq
!(r1
+ r2
, -100);
381 fn test_i128_len_doesnt_overflow() {
382 use std
::{i128, u128}
;
384 // Using parse because some versions of rust don't allow long literals
385 let octillion
: i128
= "1000000000000000000000000000".parse().unwrap();
386 let producer
= IterProducer
{
390 assert_eq
!(octillion
as u128
, producer
.range
.len());
391 assert_eq
!(octillion
as u128
, (0..octillion
).len());
392 assert_eq
!(2 * octillion
as u128
, (-octillion
..octillion
).len());
394 assert_eq
!(u128
::MAX
, (i128
::MIN
..i128
::MAX
).len());
398 fn test_u64_opt_len() {
399 use std
::{u64, usize}
;
400 assert_eq
!(Some(100), (0..100u64).into_par_iter().opt_len());
403 (0..usize::MAX
as u64).into_par_iter().opt_len()
405 if (usize::MAX
as u64) < u64::MAX
{
408 (0..(usize::MAX
as u64).wrapping_add(1))
412 assert_eq
!(None
, (0..u64::MAX
).into_par_iter().opt_len());
417 fn test_u128_opt_len() {
418 use std
::{u128, usize}
;
419 assert_eq
!(Some(100), (0..100u128).into_par_iter().opt_len());
422 (0..usize::MAX
as u128
).into_par_iter().opt_len()
424 assert_eq
!(None
, (0..1 + usize::MAX
as u128
).into_par_iter().opt_len());
425 assert_eq
!(None
, (0..u128
::MAX
).into_par_iter().opt_len());
428 // `usize as i64` can overflow, so make sure to wrap it appropriately
429 // when using the `opt_len` "indexed" mode.
431 #[cfg(target_pointer_width = "64")]
432 fn test_usize_i64_overflow() {
433 use crate::ThreadPoolBuilder
;
436 let iter
= (-2..i64::MAX
).into_par_iter();
437 assert_eq
!(iter
.opt_len(), Some(i64::MAX
as usize + 2));
439 // always run with multiple threads to split into, or this will take forever...
440 let pool
= ThreadPoolBuilder
::new().num_threads(8).build().unwrap();
441 pool
.install(|| assert_eq
!(iter
.find_last(|_
| true), Some(i64::MAX
- 1)));
445 fn test_issue_833() {
446 fn is_even(n
: i64) -> bool
{
450 // The integer type should be inferred from `is_even`
451 let v
: Vec
<_
> = (1..100).into_par_iter().filter(|&x
| is_even(x
)).collect();
452 assert
!(v
.into_iter().eq((2..100).step_by(2)));
454 // Try examples with indexed iterators too
455 let pos
= (0..100).into_par_iter().position_any(|x
| x
== 50i16);
456 assert_eq
!(pos
, Some(50usize
));
461 .all(|(a
, b
)| i16::eq(&a
, &b
)));