| 1 |
# Contributing to itertools |
| 2 |
|
| 3 |
We use stable Rust only. |
| 4 |
Please 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, |
| 7 |
then **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 |
|
| 10 |
To pass CI tests successfully, your code must be free of "compiler warnings" and "clippy warnings" and be "rustfmt" formatted. |
| 11 |
|
| 12 |
Note that small PRs are easier to review and therefore are more easily merged. |
| 13 |
|
| 14 |
## Write a new method/adaptor for `Itertools` trait |
| 15 |
In general, the code logic should be tested with [quickcheck](https://crates.io/crates/quickcheck) tests in `tests/quick.rs` |
| 16 |
which allow us to test properties about the code with randomly generated inputs. |
| 17 |
|
| 18 |
### Behind `use_std`/`use_alloc` feature? |
| 19 |
If it needs the "std" (such as using hashes) then it should be behind the `use_std` feature, |
| 20 |
or if it requires heap allocation (such as using vectors) then it should be behind the `use_alloc` feature. |
| 21 |
Otherwise it should be able to run in `no_std` context. |
| 22 |
|
| 23 |
This 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 |
| 35 |
Iterators 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 |
|
| 40 |
Those behaviors are **tested** in `tests/laziness.rs`. |
| 41 |
|
| 42 |
## Specialize `Iterator` methods |
| 43 |
It might be more performant to specialize some methods. |
| 44 |
However, each specialization should be thoroughly tested. |
| 45 |
|
| 46 |
Correctly specializing methods can be difficult, and _we do not require that you do it on your initial PR_. |
| 47 |
|
| 48 |
Most 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 |
|
| 61 |
Additionally, |
| 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 |
|
| 69 |
An adaptor might use the inner iterator specializations for its own specializations. |
| 70 |
|
| 71 |
They 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 |
| 76 |
All our iterators should implement `Debug`. |
| 77 |
|
| 78 |
When one of the field is not debuggable (such as _functions_), you must not derive `Debug`. |
| 79 |
Instead, 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 |
| 85 |
use std::fmt; |
| 86 |
|
| 87 |
/* ===== Simple derive. ===== */ |
| 88 |
#[derive(Debug)] |
| 89 |
struct Name1<I> { |
| 90 |
iter: I, |
| 91 |
} |
| 92 |
|
| 93 |
/* ===== With an unclonable field. ===== */ |
| 94 |
struct Name2<I, F> { |
| 95 |
iter: I, |
| 96 |
func: F, |
| 97 |
} |
| 98 |
|
| 99 |
// No `F: Debug` bound and the field `func` is ignored. |
| 100 |
impl<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. ===== */ |
| 106 |
struct 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. |
| 113 |
impl<I: Iterator + fmt::Debug, F> fmt::Debug for Name3<I, F> |
| 114 |
where |
| 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. ===== */ |
| 121 |
struct 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. |
| 127 |
impl<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) |
| 140 |
All our iterators should implement `Clone` when possible. |
| 141 |
|
| 142 |
Note that a mutable reference is never clonable so `struct Name<'a, I: 'a> { iter: &'a mut I }` can not implement `Clone`. |
| 143 |
|
| 144 |
Derive `Clone` on a generic struct adds the bound `Clone` on each generic parameter. |
| 145 |
It 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) |
| 148 |
This trait should be implemented _by all iterators that always return `None` after returning `None` once_, because it allows to optimize `Iterator::fuse()`. |
| 149 |
|
| 150 |
The 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 |
|
| 155 |
Therefore, we do not implement it on adaptors that makes the iterator longer as the resulting length could overflow. |
| 156 |
|
| 157 |
One 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 |
|
| 159 |
The 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) |
| 162 |
When the iterator structure allows to handle _iterating on both fronts simultaneously_. |
| 163 |
The iteration might stop in the middle when both fronts meet. |
| 164 |
|
| 165 |
The 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) |
| 168 |
TODO |
| 169 |
|
| 170 |
This is currently **tested** in `tests/test_std.rs`. |
| 171 |
|
| 172 |
## About lending iterators |
| 173 |
TODO |
| 174 |
|
| 175 |
|
| 176 |
## Other notes |
| 177 |
No guideline about using `#[inline]` yet. |
| 178 |
|
| 179 |
### `.fold` / `.for_each` / `.try_fold` / `.try_for_each` |
| 180 |
In 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 |
|
| 182 |
From [#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. |