]> git.lizzy.rs Git - rust.git/blob - src/libcore/iter/sources.rs
Rollup merge of #68361 - t6:patch-freebsd-lld-i386, r=alexcrichton
[rust.git] / src / libcore / iter / sources.rs
1 use crate::fmt;
2 use crate::marker;
3 use crate::usize;
4
5 use super::{FusedIterator, TrustedLen};
6
7 /// An iterator that repeats an element endlessly.
8 ///
9 /// This `struct` is created by the [`repeat`] function. See its documentation for more.
10 ///
11 /// [`repeat`]: fn.repeat.html
12 #[derive(Clone, Debug)]
13 #[stable(feature = "rust1", since = "1.0.0")]
14 pub struct Repeat<A> {
15     element: A,
16 }
17
18 #[stable(feature = "rust1", since = "1.0.0")]
19 impl<A: Clone> Iterator for Repeat<A> {
20     type Item = A;
21
22     #[inline]
23     fn next(&mut self) -> Option<A> {
24         Some(self.element.clone())
25     }
26     #[inline]
27     fn size_hint(&self) -> (usize, Option<usize>) {
28         (usize::MAX, None)
29     }
30 }
31
32 #[stable(feature = "rust1", since = "1.0.0")]
33 impl<A: Clone> DoubleEndedIterator for Repeat<A> {
34     #[inline]
35     fn next_back(&mut self) -> Option<A> {
36         Some(self.element.clone())
37     }
38 }
39
40 #[stable(feature = "fused", since = "1.26.0")]
41 impl<A: Clone> FusedIterator for Repeat<A> {}
42
43 #[unstable(feature = "trusted_len", issue = "37572")]
44 unsafe impl<A: Clone> TrustedLen for Repeat<A> {}
45
46 /// Creates a new iterator that endlessly repeats a single element.
47 ///
48 /// The `repeat()` function repeats a single value over and over again.
49 ///
50 /// Infinite iterators like `repeat()` are often used with adapters like
51 /// [`take`], in order to make them finite.
52 ///
53 /// [`take`]: trait.Iterator.html#method.take
54 ///
55 /// If the element type of the iterator you need does not implement `Clone`,
56 /// or if you do not want to keep the repeated element in memory, you can
57 /// instead use the [`repeat_with`] function.
58 ///
59 /// [`repeat_with`]: fn.repeat_with.html
60 ///
61 /// # Examples
62 ///
63 /// Basic usage:
64 ///
65 /// ```
66 /// use std::iter;
67 ///
68 /// // the number four 4ever:
69 /// let mut fours = iter::repeat(4);
70 ///
71 /// assert_eq!(Some(4), fours.next());
72 /// assert_eq!(Some(4), fours.next());
73 /// assert_eq!(Some(4), fours.next());
74 /// assert_eq!(Some(4), fours.next());
75 /// assert_eq!(Some(4), fours.next());
76 ///
77 /// // yup, still four
78 /// assert_eq!(Some(4), fours.next());
79 /// ```
80 ///
81 /// Going finite with [`take`]:
82 ///
83 /// ```
84 /// use std::iter;
85 ///
86 /// // that last example was too many fours. Let's only have four fours.
87 /// let mut four_fours = iter::repeat(4).take(4);
88 ///
89 /// assert_eq!(Some(4), four_fours.next());
90 /// assert_eq!(Some(4), four_fours.next());
91 /// assert_eq!(Some(4), four_fours.next());
92 /// assert_eq!(Some(4), four_fours.next());
93 ///
94 /// // ... and now we're done
95 /// assert_eq!(None, four_fours.next());
96 /// ```
97 #[inline]
98 #[stable(feature = "rust1", since = "1.0.0")]
99 pub fn repeat<T: Clone>(elt: T) -> Repeat<T> {
100     Repeat { element: elt }
101 }
102
103 /// An iterator that repeats elements of type `A` endlessly by
104 /// applying the provided closure `F: FnMut() -> A`.
105 ///
106 /// This `struct` is created by the [`repeat_with`] function.
107 /// See its documentation for more.
108 ///
109 /// [`repeat_with`]: fn.repeat_with.html
110 #[derive(Copy, Clone, Debug)]
111 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
112 pub struct RepeatWith<F> {
113     repeater: F,
114 }
115
116 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
117 impl<A, F: FnMut() -> A> Iterator for RepeatWith<F> {
118     type Item = A;
119
120     #[inline]
121     fn next(&mut self) -> Option<A> {
122         Some((self.repeater)())
123     }
124
125     #[inline]
126     fn size_hint(&self) -> (usize, Option<usize>) {
127         (usize::MAX, None)
128     }
129 }
130
131 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
132 impl<A, F: FnMut() -> A> FusedIterator for RepeatWith<F> {}
133
134 #[unstable(feature = "trusted_len", issue = "37572")]
135 unsafe impl<A, F: FnMut() -> A> TrustedLen for RepeatWith<F> {}
136
137 /// Creates a new iterator that repeats elements of type `A` endlessly by
138 /// applying the provided closure, the repeater, `F: FnMut() -> A`.
139 ///
140 /// The `repeat_with()` function calls the repeater over and over again.
141 ///
142 /// Infinite iterators like `repeat_with()` are often used with adapters like
143 /// [`take`], in order to make them finite.
144 ///
145 /// [`take`]: trait.Iterator.html#method.take
146 ///
147 /// If the element type of the iterator you need implements `Clone`, and
148 /// it is OK to keep the source element in memory, you should instead use
149 /// the [`repeat`] function.
150 ///
151 /// [`repeat`]: fn.repeat.html
152 ///
153 /// An iterator produced by `repeat_with()` is not a `DoubleEndedIterator`.
154 /// If you need `repeat_with()` to return a `DoubleEndedIterator`,
155 /// please open a GitHub issue explaining your use case.
156 ///
157 /// # Examples
158 ///
159 /// Basic usage:
160 ///
161 /// ```
162 /// use std::iter;
163 ///
164 /// // let's assume we have some value of a type that is not `Clone`
165 /// // or which don't want to have in memory just yet because it is expensive:
166 /// #[derive(PartialEq, Debug)]
167 /// struct Expensive;
168 ///
169 /// // a particular value forever:
170 /// let mut things = iter::repeat_with(|| Expensive);
171 ///
172 /// assert_eq!(Some(Expensive), things.next());
173 /// assert_eq!(Some(Expensive), things.next());
174 /// assert_eq!(Some(Expensive), things.next());
175 /// assert_eq!(Some(Expensive), things.next());
176 /// assert_eq!(Some(Expensive), things.next());
177 /// ```
178 ///
179 /// Using mutation and going finite:
180 ///
181 /// ```rust
182 /// use std::iter;
183 ///
184 /// // From the zeroth to the third power of two:
185 /// let mut curr = 1;
186 /// let mut pow2 = iter::repeat_with(|| { let tmp = curr; curr *= 2; tmp })
187 ///                     .take(4);
188 ///
189 /// assert_eq!(Some(1), pow2.next());
190 /// assert_eq!(Some(2), pow2.next());
191 /// assert_eq!(Some(4), pow2.next());
192 /// assert_eq!(Some(8), pow2.next());
193 ///
194 /// // ... and now we're done
195 /// assert_eq!(None, pow2.next());
196 /// ```
197 #[inline]
198 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
199 pub fn repeat_with<A, F: FnMut() -> A>(repeater: F) -> RepeatWith<F> {
200     RepeatWith { repeater }
201 }
202
203 /// An iterator that yields nothing.
204 ///
205 /// This `struct` is created by the [`empty`] function. See its documentation for more.
206 ///
207 /// [`empty`]: fn.empty.html
208 #[stable(feature = "iter_empty", since = "1.2.0")]
209 pub struct Empty<T>(marker::PhantomData<T>);
210
211 #[stable(feature = "iter_empty_send_sync", since = "1.42.0")]
212 unsafe impl<T> Send for Empty<T> {}
213 #[stable(feature = "iter_empty_send_sync", since = "1.42.0")]
214 unsafe impl<T> Sync for Empty<T> {}
215
216 #[stable(feature = "core_impl_debug", since = "1.9.0")]
217 impl<T> fmt::Debug for Empty<T> {
218     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
219         f.pad("Empty")
220     }
221 }
222
223 #[stable(feature = "iter_empty", since = "1.2.0")]
224 impl<T> Iterator for Empty<T> {
225     type Item = T;
226
227     fn next(&mut self) -> Option<T> {
228         None
229     }
230
231     fn size_hint(&self) -> (usize, Option<usize>) {
232         (0, Some(0))
233     }
234 }
235
236 #[stable(feature = "iter_empty", since = "1.2.0")]
237 impl<T> DoubleEndedIterator for Empty<T> {
238     fn next_back(&mut self) -> Option<T> {
239         None
240     }
241 }
242
243 #[stable(feature = "iter_empty", since = "1.2.0")]
244 impl<T> ExactSizeIterator for Empty<T> {
245     fn len(&self) -> usize {
246         0
247     }
248 }
249
250 #[unstable(feature = "trusted_len", issue = "37572")]
251 unsafe impl<T> TrustedLen for Empty<T> {}
252
253 #[stable(feature = "fused", since = "1.26.0")]
254 impl<T> FusedIterator for Empty<T> {}
255
256 // not #[derive] because that adds a Clone bound on T,
257 // which isn't necessary.
258 #[stable(feature = "iter_empty", since = "1.2.0")]
259 impl<T> Clone for Empty<T> {
260     fn clone(&self) -> Empty<T> {
261         Empty(marker::PhantomData)
262     }
263 }
264
265 // not #[derive] because that adds a Default bound on T,
266 // which isn't necessary.
267 #[stable(feature = "iter_empty", since = "1.2.0")]
268 impl<T> Default for Empty<T> {
269     fn default() -> Empty<T> {
270         Empty(marker::PhantomData)
271     }
272 }
273
274 /// Creates an iterator that yields nothing.
275 ///
276 /// # Examples
277 ///
278 /// Basic usage:
279 ///
280 /// ```
281 /// use std::iter;
282 ///
283 /// // this could have been an iterator over i32, but alas, it's just not.
284 /// let mut nope = iter::empty::<i32>();
285 ///
286 /// assert_eq!(None, nope.next());
287 /// ```
288 #[stable(feature = "iter_empty", since = "1.2.0")]
289 #[rustc_const_stable(feature = "const_iter_empty", since = "1.32.0")]
290 pub const fn empty<T>() -> Empty<T> {
291     Empty(marker::PhantomData)
292 }
293
294 /// An iterator that yields an element exactly once.
295 ///
296 /// This `struct` is created by the [`once`] function. See its documentation for more.
297 ///
298 /// [`once`]: fn.once.html
299 #[derive(Clone, Debug)]
300 #[stable(feature = "iter_once", since = "1.2.0")]
301 pub struct Once<T> {
302     inner: crate::option::IntoIter<T>,
303 }
304
305 #[stable(feature = "iter_once", since = "1.2.0")]
306 impl<T> Iterator for Once<T> {
307     type Item = T;
308
309     fn next(&mut self) -> Option<T> {
310         self.inner.next()
311     }
312
313     fn size_hint(&self) -> (usize, Option<usize>) {
314         self.inner.size_hint()
315     }
316 }
317
318 #[stable(feature = "iter_once", since = "1.2.0")]
319 impl<T> DoubleEndedIterator for Once<T> {
320     fn next_back(&mut self) -> Option<T> {
321         self.inner.next_back()
322     }
323 }
324
325 #[stable(feature = "iter_once", since = "1.2.0")]
326 impl<T> ExactSizeIterator for Once<T> {
327     fn len(&self) -> usize {
328         self.inner.len()
329     }
330 }
331
332 #[unstable(feature = "trusted_len", issue = "37572")]
333 unsafe impl<T> TrustedLen for Once<T> {}
334
335 #[stable(feature = "fused", since = "1.26.0")]
336 impl<T> FusedIterator for Once<T> {}
337
338 /// Creates an iterator that yields an element exactly once.
339 ///
340 /// This is commonly used to adapt a single value into a [`chain`] of other
341 /// kinds of iteration. Maybe you have an iterator that covers almost
342 /// everything, but you need an extra special case. Maybe you have a function
343 /// which works on iterators, but you only need to process one value.
344 ///
345 /// [`chain`]: trait.Iterator.html#method.chain
346 ///
347 /// # Examples
348 ///
349 /// Basic usage:
350 ///
351 /// ```
352 /// use std::iter;
353 ///
354 /// // one is the loneliest number
355 /// let mut one = iter::once(1);
356 ///
357 /// assert_eq!(Some(1), one.next());
358 ///
359 /// // just one, that's all we get
360 /// assert_eq!(None, one.next());
361 /// ```
362 ///
363 /// Chaining together with another iterator. Let's say that we want to iterate
364 /// over each file of the `.foo` directory, but also a configuration file,
365 /// `.foorc`:
366 ///
367 /// ```no_run
368 /// use std::iter;
369 /// use std::fs;
370 /// use std::path::PathBuf;
371 ///
372 /// let dirs = fs::read_dir(".foo").unwrap();
373 ///
374 /// // we need to convert from an iterator of DirEntry-s to an iterator of
375 /// // PathBufs, so we use map
376 /// let dirs = dirs.map(|file| file.unwrap().path());
377 ///
378 /// // now, our iterator just for our config file
379 /// let config = iter::once(PathBuf::from(".foorc"));
380 ///
381 /// // chain the two iterators together into one big iterator
382 /// let files = dirs.chain(config);
383 ///
384 /// // this will give us all of the files in .foo as well as .foorc
385 /// for f in files {
386 ///     println!("{:?}", f);
387 /// }
388 /// ```
389 #[stable(feature = "iter_once", since = "1.2.0")]
390 pub fn once<T>(value: T) -> Once<T> {
391     Once { inner: Some(value).into_iter() }
392 }
393
394 /// An iterator that yields a single element of type `A` by
395 /// applying the provided closure `F: FnOnce() -> A`.
396 ///
397 /// This `struct` is created by the [`once_with`] function.
398 /// See its documentation for more.
399 ///
400 /// [`once_with`]: fn.once_with.html
401 #[derive(Copy, Clone, Debug)]
402 #[unstable(feature = "iter_once_with", issue = "57581")]
403 pub struct OnceWith<F> {
404     gen: Option<F>,
405 }
406
407 #[unstable(feature = "iter_once_with", issue = "57581")]
408 impl<A, F: FnOnce() -> A> Iterator for OnceWith<F> {
409     type Item = A;
410
411     #[inline]
412     fn next(&mut self) -> Option<A> {
413         let f = self.gen.take()?;
414         Some(f())
415     }
416
417     #[inline]
418     fn size_hint(&self) -> (usize, Option<usize>) {
419         self.gen.iter().size_hint()
420     }
421 }
422
423 #[unstable(feature = "iter_once_with", issue = "57581")]
424 impl<A, F: FnOnce() -> A> DoubleEndedIterator for OnceWith<F> {
425     fn next_back(&mut self) -> Option<A> {
426         self.next()
427     }
428 }
429
430 #[unstable(feature = "iter_once_with", issue = "57581")]
431 impl<A, F: FnOnce() -> A> ExactSizeIterator for OnceWith<F> {
432     fn len(&self) -> usize {
433         self.gen.iter().len()
434     }
435 }
436
437 #[unstable(feature = "iter_once_with", issue = "57581")]
438 impl<A, F: FnOnce() -> A> FusedIterator for OnceWith<F> {}
439
440 #[unstable(feature = "iter_once_with", issue = "57581")]
441 unsafe impl<A, F: FnOnce() -> A> TrustedLen for OnceWith<F> {}
442
443 /// Creates an iterator that lazily generates a value exactly once by invoking
444 /// the provided closure.
445 ///
446 /// This is commonly used to adapt a single value generator into a [`chain`] of
447 /// other kinds of iteration. Maybe you have an iterator that covers almost
448 /// everything, but you need an extra special case. Maybe you have a function
449 /// which works on iterators, but you only need to process one value.
450 ///
451 /// Unlike [`once`], this function will lazily generate the value on request.
452 ///
453 /// [`once`]: fn.once.html
454 /// [`chain`]: trait.Iterator.html#method.chain
455 ///
456 /// # Examples
457 ///
458 /// Basic usage:
459 ///
460 /// ```
461 /// #![feature(iter_once_with)]
462 ///
463 /// use std::iter;
464 ///
465 /// // one is the loneliest number
466 /// let mut one = iter::once_with(|| 1);
467 ///
468 /// assert_eq!(Some(1), one.next());
469 ///
470 /// // just one, that's all we get
471 /// assert_eq!(None, one.next());
472 /// ```
473 ///
474 /// Chaining together with another iterator. Let's say that we want to iterate
475 /// over each file of the `.foo` directory, but also a configuration file,
476 /// `.foorc`:
477 ///
478 /// ```no_run
479 /// #![feature(iter_once_with)]
480 ///
481 /// use std::iter;
482 /// use std::fs;
483 /// use std::path::PathBuf;
484 ///
485 /// let dirs = fs::read_dir(".foo").unwrap();
486 ///
487 /// // we need to convert from an iterator of DirEntry-s to an iterator of
488 /// // PathBufs, so we use map
489 /// let dirs = dirs.map(|file| file.unwrap().path());
490 ///
491 /// // now, our iterator just for our config file
492 /// let config = iter::once_with(|| PathBuf::from(".foorc"));
493 ///
494 /// // chain the two iterators together into one big iterator
495 /// let files = dirs.chain(config);
496 ///
497 /// // this will give us all of the files in .foo as well as .foorc
498 /// for f in files {
499 ///     println!("{:?}", f);
500 /// }
501 /// ```
502 #[inline]
503 #[unstable(feature = "iter_once_with", issue = "57581")]
504 pub fn once_with<A, F: FnOnce() -> A>(gen: F) -> OnceWith<F> {
505     OnceWith { gen: Some(gen) }
506 }
507
508 /// Creates a new iterator where each iteration calls the provided closure
509 /// `F: FnMut() -> Option<T>`.
510 ///
511 /// This allows creating a custom iterator with any behavior
512 /// without using the more verbose syntax of creating a dedicated type
513 /// and implementing the `Iterator` trait for it.
514 ///
515 /// Note that the `FromFn` iterator doesn’t make assumptions about the behavior of the closure,
516 /// and therefore conservatively does not implement [`FusedIterator`],
517 /// or override [`Iterator::size_hint`] from its default `(0, None)`.
518 ///
519 /// [`FusedIterator`]: trait.FusedIterator.html
520 /// [`Iterator::size_hint`]: trait.Iterator.html#method.size_hint
521 ///
522 /// The closure can use captures and its environment to track state across iterations. Depending on
523 /// how the iterator is used, this may require specifying the `move` keyword on the closure.
524 ///
525 /// # Examples
526 ///
527 /// Let’s re-implement the counter iterator from [module-level documentation]:
528 ///
529 /// [module-level documentation]: index.html
530 ///
531 /// ```
532 /// let mut count = 0;
533 /// let counter = std::iter::from_fn(move || {
534 ///     // Increment our count. This is why we started at zero.
535 ///     count += 1;
536 ///
537 ///     // Check to see if we've finished counting or not.
538 ///     if count < 6 {
539 ///         Some(count)
540 ///     } else {
541 ///         None
542 ///     }
543 /// });
544 /// assert_eq!(counter.collect::<Vec<_>>(), &[1, 2, 3, 4, 5]);
545 /// ```
546 #[inline]
547 #[stable(feature = "iter_from_fn", since = "1.34.0")]
548 pub fn from_fn<T, F>(f: F) -> FromFn<F>
549 where
550     F: FnMut() -> Option<T>,
551 {
552     FromFn(f)
553 }
554
555 /// An iterator where each iteration calls the provided closure `F: FnMut() -> Option<T>`.
556 ///
557 /// This `struct` is created by the [`iter::from_fn`] function.
558 /// See its documentation for more.
559 ///
560 /// [`iter::from_fn`]: fn.from_fn.html
561 #[derive(Clone)]
562 #[stable(feature = "iter_from_fn", since = "1.34.0")]
563 pub struct FromFn<F>(F);
564
565 #[stable(feature = "iter_from_fn", since = "1.34.0")]
566 impl<T, F> Iterator for FromFn<F>
567 where
568     F: FnMut() -> Option<T>,
569 {
570     type Item = T;
571
572     #[inline]
573     fn next(&mut self) -> Option<Self::Item> {
574         (self.0)()
575     }
576 }
577
578 #[stable(feature = "iter_from_fn", since = "1.34.0")]
579 impl<F> fmt::Debug for FromFn<F> {
580     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
581         f.debug_struct("FromFn").finish()
582     }
583 }
584
585 /// Creates a new iterator where each successive item is computed based on the preceding one.
586 ///
587 /// The iterator starts with the given first item (if any)
588 /// and calls the given `FnMut(&T) -> Option<T>` closure to compute each item’s successor.
589 ///
590 /// ```
591 /// use std::iter::successors;
592 ///
593 /// let powers_of_10 = successors(Some(1_u16), |n| n.checked_mul(10));
594 /// assert_eq!(powers_of_10.collect::<Vec<_>>(), &[1, 10, 100, 1_000, 10_000]);
595 /// ```
596 #[stable(feature = "iter_successors", since = "1.34.0")]
597 pub fn successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F>
598 where
599     F: FnMut(&T) -> Option<T>,
600 {
601     // If this function returned `impl Iterator<Item=T>`
602     // it could be based on `unfold` and not need a dedicated type.
603     // However having a named `Successors<T, F>` type allows it to be `Clone` when `T` and `F` are.
604     Successors { next: first, succ }
605 }
606
607 /// An new iterator where each successive item is computed based on the preceding one.
608 ///
609 /// This `struct` is created by the [`successors`] function.
610 /// See its documentation for more.
611 ///
612 /// [`successors`]: fn.successors.html
613 #[derive(Clone)]
614 #[stable(feature = "iter_successors", since = "1.34.0")]
615 pub struct Successors<T, F> {
616     next: Option<T>,
617     succ: F,
618 }
619
620 #[stable(feature = "iter_successors", since = "1.34.0")]
621 impl<T, F> Iterator for Successors<T, F>
622 where
623     F: FnMut(&T) -> Option<T>,
624 {
625     type Item = T;
626
627     #[inline]
628     fn next(&mut self) -> Option<Self::Item> {
629         let item = self.next.take()?;
630         self.next = (self.succ)(&item);
631         Some(item)
632     }
633
634     #[inline]
635     fn size_hint(&self) -> (usize, Option<usize>) {
636         if self.next.is_some() { (1, None) } else { (0, Some(0)) }
637     }
638 }
639
640 #[stable(feature = "iter_successors", since = "1.34.0")]
641 impl<T, F> FusedIterator for Successors<T, F> where F: FnMut(&T) -> Option<T> {}
642
643 #[stable(feature = "iter_successors", since = "1.34.0")]
644 impl<T: fmt::Debug, F> fmt::Debug for Successors<T, F> {
645     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
646         f.debug_struct("Successors").field("next", &self.next).finish()
647     }
648 }