1//! Parallel iterator types for [inclusive ranges][std::range],
2//! the type for values created by `a..=b` expressions
3//!
4//! You will rarely need to interact with this module directly unless you have
5//! need to name one of the iterator types.
6//!
7//! ```
8//! use rayon::prelude::*;
9//!
10//! let r = (0..=100u64).into_par_iter()
11//! .sum();
12//!
13//! // compare result with sequential calculation
14//! assert_eq!((0..=100).sum::<u64>(), r);
15//! ```
16//!
17//! [std::range]: https://doc.rust-lang.org/core/ops/struct.RangeInclusive.html
18
19use crate::iter::plumbing::*;
20use crate::iter::*;
21use std::ops::RangeInclusive;
22
23/// Parallel iterator over an inclusive range, implemented for all integer types and `char`.
24///
25/// **Note:** The `zip` operation requires `IndexedParallelIterator`
26/// which is only implemented for `u8`, `i8`, `u16`, `i16`, and `char`.
27///
28/// ```
29/// use rayon::prelude::*;
30///
31/// let p = (0..=25u16).into_par_iter()
32/// .zip(0..=25u16)
33/// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
34/// .map(|(x, y)| x * y)
35/// .sum::<u16>();
36///
37/// let s = (0..=25u16).zip(0..=25u16)
38/// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
39/// .map(|(x, y)| x * y)
40/// .sum();
41///
42/// assert_eq!(p, s);
43/// ```
44#[derive(Debug, Clone)]
45pub struct Iter<T> {
46 range: RangeInclusive<T>,
47}
48
49impl<T> Iter<T>
50where
51 RangeInclusive<T>: Eq,
52 T: Ord + Copy,
53{
54 /// Returns `Some((start, end))` for `start..=end`, or `None` if it is exhausted.
55 ///
56 /// Note that `RangeInclusive` does not specify the bounds of an exhausted iterator,
57 /// so this is a way for us to figure out what we've got. Thankfully, all of the
58 /// integer types we care about can be trivially cloned.
59 fn bounds(&self) -> Option<(T, T)> {
60 let start: T = *self.range.start();
61 let end: T = *self.range.end();
62 if start <= end && self.range == (start..=end) {
63 // If the range is still nonempty, this is obviously true
64 // If the range is exhausted, either start > end or
65 // the range does not equal start..=end.
66 Some((start, end))
67 } else {
68 None
69 }
70 }
71}
72
73/// Implemented for ranges of all primitive integer types and `char`.
74impl<T> IntoParallelIterator for RangeInclusive<T>
75where
76 Iter<T>: ParallelIterator,
77{
78 type Item = <Iter<T> as ParallelIterator>::Item;
79 type Iter = Iter<T>;
80
81 fn into_par_iter(self) -> Self::Iter {
82 Iter { range: self }
83 }
84}
85
86/// These traits help drive integer type inference. Without them, an unknown `{integer}` type only
87/// has constraints on `Iter<{integer}>`, which will probably give up and use `i32`. By adding
88/// these traits on the item type, the compiler can see a more direct constraint to infer like
89/// `{integer}: RangeInteger`, which works better. See `test_issue_833` for an example.
90///
91/// They have to be `pub` since they're seen in the public `impl ParallelIterator` constraints, but
92/// we put them in a private modules so they're not actually reachable in our public API.
93mod private {
94 use super::*;
95
96 /// Implementation details of `ParallelIterator for Iter<Self>`
97 pub trait RangeInteger: Sized + Send {
98 private_decl! {}
99
100 fn drive_unindexed<C>(iter: Iter<Self>, consumer: C) -> C::Result
101 where
102 C: UnindexedConsumer<Self>;
103
104 fn opt_len(iter: &Iter<Self>) -> Option<usize>;
105 }
106
107 /// Implementation details of `IndexedParallelIterator for Iter<Self>`
108 pub trait IndexedRangeInteger: RangeInteger {
109 private_decl! {}
110
111 fn drive<C>(iter: Iter<Self>, consumer: C) -> C::Result
112 where
113 C: Consumer<Self>;
114
115 fn len(iter: &Iter<Self>) -> usize;
116
117 fn with_producer<CB>(iter: Iter<Self>, callback: CB) -> CB::Output
118 where
119 CB: ProducerCallback<Self>;
120 }
121}
122use private::{IndexedRangeInteger, RangeInteger};
123
124impl<T: RangeInteger> ParallelIterator for Iter<T> {
125 type Item = T;
126
127 fn drive_unindexed<C>(self, consumer: C) -> C::Result
128 where
129 C: UnindexedConsumer<T>,
130 {
131 T::drive_unindexed(self, consumer)
132 }
133
134 #[inline]
135 fn opt_len(&self) -> Option<usize> {
136 T::opt_len(self)
137 }
138}
139
140impl<T: IndexedRangeInteger> IndexedParallelIterator for Iter<T> {
141 fn drive<C>(self, consumer: C) -> C::Result
142 where
143 C: Consumer<T>,
144 {
145 T::drive(self, consumer)
146 }
147
148 #[inline]
149 fn len(&self) -> usize {
150 T::len(self)
151 }
152
153 fn with_producer<CB>(self, callback: CB) -> CB::Output
154 where
155 CB: ProducerCallback<T>,
156 {
157 T::with_producer(self, callback)
158 }
159}
160
161macro_rules! convert {
162 ( $iter:ident . $method:ident ( $( $arg:expr ),* ) ) => {
163 if let Some((start, end)) = $iter.bounds() {
164 if let Some(end) = end.checked_add(1) {
165 (start..end).into_par_iter().$method($( $arg ),*)
166 } else {
167 (start..end).into_par_iter().chain(once(end)).$method($( $arg ),*)
168 }
169 } else {
170 empty::<Self>().$method($( $arg ),*)
171 }
172 };
173}
174
175macro_rules! parallel_range_impl {
176 ( $t:ty ) => {
177 impl RangeInteger for $t {
178 private_impl! {}
179
180 fn drive_unindexed<C>(iter: Iter<$t>, consumer: C) -> C::Result
181 where
182 C: UnindexedConsumer<$t>,
183 {
184 convert!(iter.drive_unindexed(consumer))
185 }
186
187 fn opt_len(iter: &Iter<$t>) -> Option<usize> {
188 convert!(iter.opt_len())
189 }
190 }
191 };
192}
193
194macro_rules! indexed_range_impl {
195 ( $t:ty ) => {
196 parallel_range_impl! { $t }
197
198 impl IndexedRangeInteger for $t {
199 private_impl! {}
200
201 fn drive<C>(iter: Iter<$t>, consumer: C) -> C::Result
202 where
203 C: Consumer<$t>,
204 {
205 convert!(iter.drive(consumer))
206 }
207
208 fn len(iter: &Iter<$t>) -> usize {
209 iter.range.len()
210 }
211
212 fn with_producer<CB>(iter: Iter<$t>, callback: CB) -> CB::Output
213 where
214 CB: ProducerCallback<$t>,
215 {
216 convert!(iter.with_producer(callback))
217 }
218 }
219 };
220}
221
222// all RangeInclusive<T> with ExactSizeIterator
223indexed_range_impl! {u8}
224indexed_range_impl! {u16}
225indexed_range_impl! {i8}
226indexed_range_impl! {i16}
227
228// other RangeInclusive<T> with just Iterator
229parallel_range_impl! {usize}
230parallel_range_impl! {isize}
231parallel_range_impl! {u32}
232parallel_range_impl! {i32}
233parallel_range_impl! {u64}
234parallel_range_impl! {i64}
235parallel_range_impl! {u128}
236parallel_range_impl! {i128}
237
238// char is special
239macro_rules! convert_char {
240 ( $self:ident . $method:ident ( $( $arg:expr ),* ) ) => {
241 if let Some((start, end)) = $self.bounds() {
242 let start = start as u32;
243 let end = end as u32;
244 if start < 0xD800 && 0xE000 <= end {
245 // chain the before and after surrogate range fragments
246 (start..0xD800)
247 .into_par_iter()
248 .chain(0xE000..end + 1) // cannot use RangeInclusive, so add one to end
249 .map(|codepoint| unsafe { char::from_u32_unchecked(codepoint) })
250 .$method($( $arg ),*)
251 } else {
252 // no surrogate range to worry about
253 (start..end + 1) // cannot use RangeInclusive, so add one to end
254 .into_par_iter()
255 .map(|codepoint| unsafe { char::from_u32_unchecked(codepoint) })
256 .$method($( $arg ),*)
257 }
258 } else {
259 empty::<char>().$method($( $arg ),*)
260 }
261 };
262}
263
264impl ParallelIterator for Iter<char> {
265 type Item = char;
266
267 fn drive_unindexed<C>(self, consumer: C) -> C::Result
268 where
269 C: UnindexedConsumer<Self::Item>,
270 {
271 convert_char!(self.drive(consumer))
272 }
273
274 fn opt_len(&self) -> Option<usize> {
275 Some(self.len())
276 }
277}
278
279// Range<u32> is broken on 16 bit platforms, may as well benefit from it
280impl IndexedParallelIterator for Iter<char> {
281 // Split at the surrogate range first if we're allowed to
282 fn drive<C>(self, consumer: C) -> C::Result
283 where
284 C: Consumer<Self::Item>,
285 {
286 convert_char!(self.drive(consumer))
287 }
288
289 fn len(&self) -> usize {
290 if let Some((start, end)) = self.bounds() {
291 // Taken from <char as Step>::steps_between
292 let start = start as u32;
293 let end = end as u32;
294 let mut count = end - start;
295 if start < 0xD800 && 0xE000 <= end {
296 count -= 0x800
297 }
298 (count + 1) as usize // add one for inclusive
299 } else {
300 0
301 }
302 }
303
304 fn with_producer<CB>(self, callback: CB) -> CB::Output
305 where
306 CB: ProducerCallback<Self::Item>,
307 {
308 convert_char!(self.with_producer(callback))
309 }
310}
311
312#[test]
313#[cfg(target_pointer_width = "64")]
314fn test_u32_opt_len() {
315 assert_eq!(Some(101), (0..=100u32).into_par_iter().opt_len());
316 assert_eq!(
317 Some(u32::MAX as usize),
318 (0..=u32::MAX - 1).into_par_iter().opt_len()
319 );
320 assert_eq!(
321 Some(u32::MAX as usize + 1),
322 (0..=u32::MAX).into_par_iter().opt_len()
323 );
324}
325
326#[test]
327fn test_u64_opt_len() {
328 assert_eq!(Some(101), (0..=100u64).into_par_iter().opt_len());
329 assert_eq!(
330 Some(usize::MAX),
331 (0..=usize::MAX as u64 - 1).into_par_iter().opt_len()
332 );
333 assert_eq!(None, (0..=usize::MAX as u64).into_par_iter().opt_len());
334 assert_eq!(None, (0..=u64::MAX).into_par_iter().opt_len());
335}
336
337#[test]
338fn test_u128_opt_len() {
339 assert_eq!(Some(101), (0..=100u128).into_par_iter().opt_len());
340 assert_eq!(
341 Some(usize::MAX),
342 (0..=usize::MAX as u128 - 1).into_par_iter().opt_len()
343 );
344 assert_eq!(None, (0..=usize::MAX as u128).into_par_iter().opt_len());
345 assert_eq!(None, (0..=u128::MAX).into_par_iter().opt_len());
346}
347
348// `usize as i64` can overflow, so make sure to wrap it appropriately
349// when using the `opt_len` "indexed" mode.
350#[test]
351#[cfg(target_pointer_width = "64")]
352fn test_usize_i64_overflow() {
353 use crate::ThreadPoolBuilder;
354
355 let iter = (-2..=i64::MAX).into_par_iter();
356 assert_eq!(iter.opt_len(), Some(i64::MAX as usize + 3));
357
358 // always run with multiple threads to split into, or this will take forever...
359 let pool = ThreadPoolBuilder::new().num_threads(8).build().unwrap();
360 pool.install(|| assert_eq!(iter.find_last(|_| true), Some(i64::MAX)));
361}
362
363#[test]
364fn test_issue_833() {
365 fn is_even(n: i64) -> bool {
366 n % 2 == 0
367 }
368
369 // The integer type should be inferred from `is_even`
370 let v: Vec<_> = (1..=100).into_par_iter().filter(|&x| is_even(x)).collect();
371 assert!(v.into_iter().eq((2..=100).step_by(2)));
372
373 // Try examples with indexed iterators too
374 let pos = (0..=100).into_par_iter().position_any(|x| x == 50i16);
375 assert_eq!(pos, Some(50usize));
376
377 assert!((0..=100)
378 .into_par_iter()
379 .zip(0..=100)
380 .all(|(a, b)| i16::eq(&a, &b)));
381}
382