1# Contributing to itertools
2
3We use stable Rust only.
4Please check the minimum version of Rust we use in `Cargo.toml`.
5
6_If you are proposing a major change to CI or a new iterator adaptor for this crate,
7then **please first file an issue** describing your proposal._
8[Usual concerns about new methods](https://github.com/rust-itertools/itertools/issues/413#issuecomment-657670781).
9
10To pass CI tests successfully, your code must be free of "compiler warnings" and "clippy warnings" and be "rustfmt" formatted.
11
12Note that small PRs are easier to review and therefore are more easily merged.
13
14## Write a new method/adaptor for `Itertools` trait
15In general, the code logic should be tested with [quickcheck](https://crates.io/crates/quickcheck) tests in `tests/quick.rs`
16which allow us to test properties about the code with randomly generated inputs.
17
18### Behind `use_std`/`use_alloc` feature?
19If it needs the "std" (such as using hashes) then it should be behind the `use_std` feature,
20or if it requires heap allocation (such as using vectors) then it should be behind the `use_alloc` feature.
21Otherwise it should be able to run in `no_std` context.
22
23This mostly applies to your new module, each import from it, and to your new `Itertools` method.
24
25### Pick the right receiver
26`self`, `&mut self` or `&self`? From [#710](https://github.com/rust-itertools/itertools/pull/710):
27
28- Take by value when:
29    - It transfers ownership to another iterator type, such as `filter`, `map`...
30    - It consumes the iterator completely, such as `count`, `last`, `max`...
31- Mutably borrow when it consumes only part of the iterator, such as `find`, `all`, `try_collect`...
32- Immutably borrow when there is no change, such as `size_hint`.
33
34### Laziness
35Iterators are [lazy](https://doc.rust-lang.org/std/iter/index.html#laziness):
36
37- structs of iterator adaptors should have `#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]` ;
38- structs of iterators should have `#[must_use = "iterators are lazy and do nothing unless consumed"]`.
39
40Those behaviors are **tested** in `tests/laziness.rs`.
41
42## Specialize `Iterator` methods
43It might be more performant to specialize some methods.
44However, each specialization should be thoroughly tested.
45
46Correctly specializing methods can be difficult, and _we do not require that you do it on your initial PR_.
47
48Most of the time, we want specializations of:
49
50- [`size_hint`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.size_hint):
51  It mostly allows allocation optimizations.
52  When always exact, it also enables to implement `ExactSizeIterator`.
53  See our private module `src/size_hint.rs` for helpers.
54- [`fold`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.fold)
55  might make iteration faster than calling `next` repeatedly.
56- [`count`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.count),
57  [`last`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.last),
58  [`nth`](https://doc.rust-lang.org/std/iter/trait.Iterator.html#method.nth)
59  as we might be able to avoid iterating on every item with `next`.
60
61Additionally,
62
63- `for_each`, `reduce`, `max/min[_by[_key]]` and `partition` all rely on `fold` so you should specialize it instead.
64- `all`, `any`, `find`, `find_map`, `cmp`, `partial_cmp`, `eq`, `ne`, `lt`, `le`, `gt`, `ge` and `position` all rely (by default) on `try_fold`
65  which we can not specialize on stable rust, so you might want to wait it stabilizes
66  or specialize each of them.
67- `DoubleEndedIterator::{nth_back, rfold, rfind}`: similar reasoning.
68
69An adaptor might use the inner iterator specializations for its own specializations.
70
71They are **tested** in `tests/specializations.rs` and **benchmarked** in `benches/specializations.rs`
72(build those benchmarks is slow so you might want to temporarily remove the ones you do not want to measure).
73
74## Additional implementations
75### The [`Debug`](https://doc.rust-lang.org/std/fmt/trait.Debug.html) implementation
76All our iterators should implement `Debug`.
77
78When one of the field is not debuggable (such as _functions_), you must not derive `Debug`.
79Instead, manually implement it and _ignore this field_ in our helper macro `debug_fmt_fields`.
80
81<details>
82<summary>4 examples (click to expand)</summary>
83
84```rust
85use std::fmt;
86
87/* ===== Simple derive. ===== */
88#[derive(Debug)]
89struct Name1<I> {
90    iter: I,
91}
92
93/* ===== With an unclonable field. ===== */
94struct Name2<I, F> {
95    iter: I,
96    func: F,
97}
98
99// No `F: Debug` bound and the field `func` is ignored.
100impl<I: fmt::Debug, F> fmt::Debug for Name2<I, F> {
101    // it defines the `fmt` function from a struct name and the fields you want to debug.
102    debug_fmt_fields!(Name2, iter);
103}
104
105/* ===== With an unclonable field, but another bound to add. ===== */
106struct Name3<I: Iterator, F> {
107    iter: I,
108    item: Option<I::Item>,
109    func: F,
110}
111
112// Same about `F` and `func`, similar about `I` but we must add the `I::Item: Debug` bound.
113impl<I: Iterator + fmt::Debug, F> fmt::Debug for Name3<I, F>
114where
115    I::Item: fmt::Debug,
116{
117    debug_fmt_fields!(Name3, iter, item);
118}
119
120/* ===== With an unclonable field for which we can provide some information. ===== */
121struct Name4<I, F> {
122    iter: I,
123    func: Option<F>,
124}
125
126// If ignore a field is not good enough, implement Debug fully manually.
127impl<I: fmt::Debug, F> fmt::Debug for Name4<I, F> {
128    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
129        let func = if self.func.is_some() { "Some(_)" } else { "None" };
130        f.debug_struct("Name4")
131            .field("iter", &self.iter)
132            .field("func", &func)
133            .finish()
134    }
135}
136```
137</details>
138
139### When/How to implement [`Clone`](https://doc.rust-lang.org/std/clone/trait.Clone.html)
140All our iterators should implement `Clone` when possible.
141
142Note that a mutable reference is never clonable so `struct Name<'a, I: 'a> { iter: &'a mut I }` can not implement `Clone`.
143
144Derive `Clone` on a generic struct adds the bound `Clone` on each generic parameter.
145It might be an issue in which case you should manually implement it with our helper macro `clone_fields` (it defines the `clone` function calling `clone` on each field) and be careful about the bounds.
146
147### When to implement [`std::iter::FusedIterator`](https://doc.rust-lang.org/std/iter/trait.FusedIterator.html)
148This trait should be implemented _by all iterators that always return `None` after returning `None` once_, because it allows to optimize `Iterator::fuse()`.
149
150The conditions on which it should be implemented are usually the ones from the `Iterator` implementation, eventually refined to ensure it behaves in a fused way.
151
152### When to implement [`ExactSizeIterator`](https://doc.rust-lang.org/std/iter/trait.ExactSizeIterator.html)
153_When we are always able to return an exact non-overflowing length._
154
155Therefore, we do not implement it on adaptors that makes the iterator longer as the resulting length could overflow.
156
157One should not override `ExactSizeIterator::len` method but rely on an exact `Iterator::size_hint` implementation, meaning it returns `(length, Some(length))` (unless you could make `len` more performant than the default).
158
159The conditions on which it should be implemented are usually the ones from the `Iterator` implementation, probably refined to ensure the size hint is exact.
160
161### When to implement [`DoubleEndedIterator`](https://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html)
162When the iterator structure allows to handle _iterating on both fronts simultaneously_.
163The iteration might stop in the middle when both fronts meet.
164
165The conditions on which it should be implemented are usually the ones from the `Iterator` implementation, probably refined to ensure we can iterate on both fronts simultaneously.
166
167### When to implement [`itertools::PeekingNext`](https://docs.rs/itertools/latest/itertools/trait.PeekingNext.html)
168TODO
169
170This is currently **tested** in `tests/test_std.rs`.
171
172## About lending iterators
173TODO
174
175
176## Other notes
177No guideline about using `#[inline]` yet.
178
179### `.fold` / `.for_each` / `.try_fold` / `.try_for_each`
180In the Rust standard library, it's quite common for `fold` to be implemented in terms of `try_fold`. But it's not something we do yet because we can not specialize `try_fold` methods yet (it uses the unstable `Try`).
181
182From [#781](https://github.com/rust-itertools/itertools/pull/781), the general rule to follow is something like this:
183
184- If you need to completely consume an iterator:
185  - Use `fold` if you need an _owned_ access to an accumulator.
186  - Use `for_each` otherwise.
187- If you need to partly consume an iterator, the same applies with `try_` versions:
188  - Use `try_fold` if you need an _owned_ access to an accumulator.
189  - Use `try_for_each` otherwise.
190