Debian Codegraph @

.cargo/vendor/rayon/src/range.rs

raw
1 //! Parallel iterator types for [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.Range.html
18
19 use crate::iter::plumbing::*;
20 use crate::iter::*;
21 use std::ops::Range;
22
23 /// Parallel iterator over a range, implemented for all integer types and `char`.
24 ///
25 /// **Note:** The `zip` operation requires `IndexedParallelIterator`
26 /// which is not implemented for `u64`, `i64`, `u128`, or `i128`.
27 ///
28 /// ```
29 /// use rayon::prelude::*;
30 ///
31 /// let p = (0..25usize).into_par_iter()
32 /// .zip(0..25usize)
33 /// .filter(|&(x, y)| x % 5 == 0 || y % 5 == 0)
34 /// .map(|(x, y)| x * y)
35 /// .sum::<usize>();
36 ///
37 /// let s = (0..25usize).zip(0..25)
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)]
45 pub struct Iter<T> {
46 range: Range<T>,
47 }
48
49 /// Implemented for ranges of all primitive integer types and `char`.
50 impl<T> IntoParallelIterator for Range<T>
51 where
52 Iter<T>: ParallelIterator,
53 {
54 type Item = <Iter<T> as ParallelIterator>::Item;
55 type Iter = Iter<T>;
56
57 fn into_par_iter(self) -> Self::Iter {
58 Iter { range: self }
59 }
60 }
61
62 struct IterProducer<T> {
63 range: Range<T>,
64 }
65
66 impl<T> IntoIterator for IterProducer<T>
67 where
68 Range<T>: Iterator,
69 {
70 type Item = <Range<T> as Iterator>::Item;
71 type IntoIter = Range<T>;
72
73 fn into_iter(self) -> Self::IntoIter {
74 self.range
75 }
76 }
77
78 /// These traits help drive integer type inference. Without them, an unknown `{integer}` type only
79 /// has constraints on `Iter<{integer}>`, which will probably give up and use `i32`. By adding
80 /// these traits on the item type, the compiler can see a more direct constraint to infer like
81 /// `{integer}: RangeInteger`, which works better. See `test_issue_833` for an example.
82 ///
83 /// They have to be `pub` since they're seen in the public `impl ParallelIterator` constraints, but
84 /// we put them in a private modules so they're not actually reachable in our public API.
85 mod private {
86 use super::*;
87
88 /// Implementation details of `ParallelIterator for Iter<Self>`
89 pub trait RangeInteger: Sized + Send {
90 private_decl! {}
91
92 fn drive_unindexed<C>(iter: Iter<Self>, consumer: C) -> C::Result
93 where
94 C: UnindexedConsumer<Self>;
95
96 fn opt_len(iter: &Iter<Self>) -> Option<usize>;
97 }
98
99 /// Implementation details of `IndexedParallelIterator for Iter<Self>`
100 pub trait IndexedRangeInteger: RangeInteger {
101 private_decl! {}
102
103 fn drive<C>(iter: Iter<Self>, consumer: C) -> C::Result
104 where
105 C: Consumer<Self>;
106
107 fn len(iter: &Iter<Self>) -> usize;
108
109 fn with_producer<CB>(iter: Iter<Self>, callback: CB) -> CB::Output
110 where
111 CB: ProducerCallback<Self>;
112 }
113 }
114 use private::{IndexedRangeInteger, RangeInteger};
115
116 impl<T: RangeInteger> ParallelIterator for Iter<T> {
117 type Item = T;
118
119 fn drive_unindexed<C>(self, consumer: C) -> C::Result
120 where
121 C: UnindexedConsumer<T>,
122 {
123 T::drive_unindexed(self, consumer)
124 }
125
126 #[inline]
127 fn opt_len(&self) -> Option<usize> {
128 T::opt_len(self)
129 }
130 }
131
132 impl<T: IndexedRangeInteger> IndexedParallelIterator for Iter<T> {
133 fn drive<C>(self, consumer: C) -> C::Result
134 where
135 C: Consumer<T>,
136 {
137 T::drive(self, consumer)
138 }
139
140 #[inline]
141 fn len(&self) -> usize {
142 T::len(self)
143 }
144
145 fn with_producer<CB>(self, callback: CB) -> CB::Output
146 where
147 CB: ProducerCallback<T>,
148 {
149 T::with_producer(self, callback)
150 }
151 }
152
153 macro_rules! indexed_range_impl {
154 ( $t:ty ) => {
155 impl RangeInteger for $t {
156 private_impl! {}
157
158 fn drive_unindexed<C>(iter: Iter<$t>, consumer: C) -> C::Result
159 where
160 C: UnindexedConsumer<$t>,
161 {
162 bridge(iter, consumer)
163 }
164
165 fn opt_len(iter: &Iter<$t>) -> Option<usize> {
166 Some(iter.range.len())
167 }
168 }
169
170 impl IndexedRangeInteger for $t {
171 private_impl! {}
172
173 fn drive<C>(iter: Iter<$t>, consumer: C) -> C::Result
174 where
175 C: Consumer<$t>,
176 {
177 bridge(iter, consumer)
178 }
179
180 fn len(iter: &Iter<$t>) -> usize {
181 iter.range.len()
182 }
183
184 fn with_producer<CB>(iter: Iter<$t>, callback: CB) -> CB::Output
185 where
186 CB: ProducerCallback<$t>,
187 {
188 callback.callback(IterProducer { range: iter.range })
189 }
190 }
191
192 impl Producer for IterProducer<$t> {
193 type Item = <Range<$t> as Iterator>::Item;
194 type IntoIter = Range<$t>;
195 fn into_iter(self) -> Self::IntoIter {
196 self.range
197 }
198
199 fn split_at(self, index: usize) -> (Self, Self) {
200 assert!(index <= self.range.len());
201 // For signed $t, the length and requested index could be greater than $t::MAX, and
202 // then `index as $t` could wrap to negative, so wrapping_add is necessary.
203 let mid = self.range.start.wrapping_add(index as $t);
204 let left = self.range.start..mid;
205 let right = mid..self.range.end;
206 (IterProducer { range: left }, IterProducer { range: right })
207 }
208 }
209 };
210 }
211
212 trait UnindexedRangeLen<L> {
213 fn len(&self) -> L;
214 }
215
216 macro_rules! unindexed_range_impl {
217 ( $t:ty, $len_t:ty ) => {
218 impl UnindexedRangeLen<$len_t> for Range<$t> {
219 fn len(&self) -> $len_t {
220 let &Range { start, end } = self;
221 if end > start {
222 end.wrapping_sub(start) as $len_t
223 } else {
224 0
225 }
226 }
227 }
228
229 impl RangeInteger for $t {
230 private_impl! {}
231
232 fn drive_unindexed<C>(iter: Iter<$t>, consumer: C) -> C::Result
233 where
234 C: UnindexedConsumer<$t>,
235 {
236 #[inline]
237 fn offset(start: $t) -> impl Fn(usize) -> $t {
238 move |i| start.wrapping_add(i as $t)
239 }
240
241 if let Some(len) = iter.opt_len() {
242 // Drive this in indexed mode for better `collect`.
243 (0..len)
244 .into_par_iter()
245 .map(offset(iter.range.start))
246 .drive(consumer)
247 } else {
248 bridge_unindexed(IterProducer { range: iter.range }, consumer)
249 }
250 }
251
252 fn opt_len(iter: &Iter<$t>) -> Option<usize> {
253 usize::try_from(iter.range.len()).ok()
254 }
255 }
256
257 impl UnindexedProducer for IterProducer<$t> {
258 type Item = $t;
259
260 fn split(mut self) -> (Self, Option<Self>) {
261 let index = self.range.len() / 2;
262 if index > 0 {
263 let mid = self.range.start.wrapping_add(index as $t);
264 let right = mid..self.range.end;
265 self.range.end = mid;
266 (self, Some(IterProducer { range: right }))
267 } else {
268 (self, None)
269 }
270 }
271
272 fn fold_with<F>(self, folder: F) -> F
273 where
274 F: Folder<Self::Item>,
275 {
276 folder.consume_iter(self)
277 }
278 }
279 };
280 }
281
282 // all Range<T> with ExactSizeIterator
283 indexed_range_impl! {u8}
284 indexed_range_impl! {u16}
285 indexed_range_impl! {u32}
286 indexed_range_impl! {usize}
287 indexed_range_impl! {i8}
288 indexed_range_impl! {i16}
289 indexed_range_impl! {i32}
290 indexed_range_impl! {isize}
291
292 // other Range<T> with just Iterator
293 unindexed_range_impl! {u64, u64}
294 unindexed_range_impl! {i64, u64}
295 unindexed_range_impl! {u128, u128}
296 unindexed_range_impl! {i128, u128}
297
298 // char is special because of the surrogate range hole
299 macro_rules! convert_char {
300 ( $self:ident . $method:ident ( $( $arg:expr ),* ) ) => {{
301 let start = $self.range.start as u32;
302 let end = $self.range.end as u32;
303 if start < 0xD800 && 0xE000 < end {
304 // chain the before and after surrogate range fragments
305 (start..0xD800)
306 .into_par_iter()
307 .chain(0xE000..end)
308 .map(|codepoint| unsafe { char::from_u32_unchecked(codepoint) })
309 .$method($( $arg ),*)
310 } else {
311 // no surrogate range to worry about
312 (start..end)
313 .into_par_iter()
314 .map(|codepoint| unsafe { char::from_u32_unchecked(codepoint) })
315 .$method($( $arg ),*)
316 }
317 }};
318 }
319
320 impl ParallelIterator for Iter<char> {
321 type Item = char;
322
323 fn drive_unindexed<C>(self, consumer: C) -> C::Result
324 where
325 C: UnindexedConsumer<Self::Item>,
326 {
327 convert_char!(self.drive(consumer))
328 }
329
330 fn opt_len(&self) -> Option<usize> {
331 Some(self.len())
332 }
333 }
334
335 impl IndexedParallelIterator for Iter<char> {
336 // Split at the surrogate range first if we're allowed to
337 fn drive<C>(self, consumer: C) -> C::Result
338 where
339 C: Consumer<Self::Item>,
340 {
341 convert_char!(self.drive(consumer))
342 }
343
344 fn len(&self) -> usize {
345 // Taken from <char as Step>::steps_between
346 let start = self.range.start as u32;
347 let end = self.range.end as u32;
348 if start < end {
349 let mut count = end - start;
350 if start < 0xD800 && 0xE000 <= end {
351 count -= 0x800
352 }
353 count as usize
354 } else {
355 0
356 }
357 }
358
359 fn with_producer<CB>(self, callback: CB) -> CB::Output
360 where
361 CB: ProducerCallback<Self::Item>,
362 {
363 convert_char!(self.with_producer(callback))
364 }
365 }
366
367 #[test]
368 fn check_range_split_at_overflow() {
369 // Note, this split index overflows i8!
370 let producer = IterProducer { range: -100i8..100 };
371 let (left, right) = producer.split_at(150);
372 let r1: i32 = left.range.map(i32::from).sum();
373 let r2: i32 = right.range.map(i32::from).sum();
374 assert_eq!(r1 + r2, -100);
375 }
376
377 #[test]
378 fn test_i128_len_doesnt_overflow() {
379 // Using parse because some versions of rust don't allow long literals
380 let octillion: i128 = "1000000000000000000000000000".parse().unwrap();
381 let producer = IterProducer {
382 range: 0..octillion,
383 };
384
385 assert_eq!(octillion as u128, producer.range.len());
386 assert_eq!(octillion as u128, (0..octillion).len());
387 assert_eq!(2 * octillion as u128, (-octillion..octillion).len());
388
389 assert_eq!(u128::MAX, (i128::MIN..i128::MAX).len());
390 }
391
392 #[test]
393 fn test_u64_opt_len() {
394 assert_eq!(Some(100), (0..100u64).into_par_iter().opt_len());
395 assert_eq!(
396 Some(usize::MAX),
397 (0..usize::MAX as u64).into_par_iter().opt_len()
398 );
399 if (usize::MAX as u64) < u64::MAX {
400 assert_eq!(
401 None,
402 (0..(usize::MAX as u64).wrapping_add(1))
403 .into_par_iter()
404 .opt_len()
405 );
406 assert_eq!(None, (0..u64::MAX).into_par_iter().opt_len());
407 }
408 }
409
410 #[test]
411 fn test_u128_opt_len() {
412 assert_eq!(Some(100), (0..100u128).into_par_iter().opt_len());
413 assert_eq!(
414 Some(usize::MAX),
415 (0..usize::MAX as u128).into_par_iter().opt_len()
416 );
417 assert_eq!(None, (0..1 + usize::MAX as u128).into_par_iter().opt_len());
418 assert_eq!(None, (0..u128::MAX).into_par_iter().opt_len());
419 }
420
421 // `usize as i64` can overflow, so make sure to wrap it appropriately
422 // when using the `opt_len` "indexed" mode.
423 #[test]
424 #[cfg(target_pointer_width = "64")]
425 fn test_usize_i64_overflow() {
426 use crate::ThreadPoolBuilder;
427
428 let iter = (-2..i64::MAX).into_par_iter();
429 assert_eq!(iter.opt_len(), Some(i64::MAX as usize + 2));
430
431 // always run with multiple threads to split into, or this will take forever...
432 let pool = ThreadPoolBuilder::new().num_threads(8).build().unwrap();
433 pool.install(|| assert_eq!(iter.find_last(|_| true), Some(i64::MAX - 1)));
434 }
435
436 #[test]
437 fn test_issue_833() {
438 fn is_even(n: i64) -> bool {
439 n % 2 == 0
440 }
441
442 // The integer type should be inferred from `is_even`
443 let v: Vec<_> = (1..100).into_par_iter().filter(|&x| is_even(x)).collect();
444 assert!(v.into_iter().eq((2..100).step_by(2)));
445
446 // Try examples with indexed iterators too
447 let pos = (0..100).into_par_iter().position_any(|x| x == 50i16);
448 assert_eq!(pos, Some(50usize));
449
450 assert!((0..100)
451 .into_par_iter()
452 .zip(0..100)
453 .all(|(a, b)| i16::eq(&a, &b)));
454 }