| Age | Commit message (Collapse) | Author | Lines |
|---|
|
|
|
|
|
Add Peekable::next_if
Prior art:
`rust_analyzer` uses [`Parser::eat`](https://github.com/rust-analyzer/rust-analyzer/blob/50f4ae798b7c54d417ee88455b87fd0477473150/crates/ra_parser/src/parser.rs#L94), which is `next_if` specialized to `|y| self.next_if(|x| x == y)`.
Basically every other parser I've run into in Rust has an equivalent of `Parser::eat`; see for example
- [cranelift](https://github.com/bytecodealliance/wasmtime/blob/94190d57244b26baf36629c88104b0ba516510cf/cranelift/reader/src/parser.rs#L498)
- [rcc](https://github.com/jyn514/rcc/blob/a8159c3904a0c950fbba817bf9109023fad69033/src/parse/mod.rs#L231)
- [crunch](https://github.com/Kixiron/crunch-lang/blob/8521874fab8a7d62bfa7dea8bd1da94b63e31be8/crates/crunch-parser/src/parser/mod.rs#L213-L241)
Possible extensions: A specialization of `next_if` to using `Eq::eq`. The only difficulty here is the naming - maybe `next_if_eq`?
Alternatives:
- Instead of `func: impl FnOnce(&I::Item) -> bool`, use `func: impl FnOnce(I::Item) -> Option<I::Item>`. This has the advantage that `func` can move the value if necessary, but means that there is no guarantee `func` will return the same value it was given.
- Instead of `fn next_if(...) -> Option<I::Item>`, use `fn next_if(...) -> bool`. This makes the common case of `iter.next_if(f).is_some()` easier, but makes the unusual case impossible.
Bikeshedding on naming:
- `next_if` could be renamed to `consume_if` (to match `eat`, but a little more formally)
- `next_if_eq` could be renamed to `consume`. This is more concise but less self-explanatory if you haven't written a lot of parsers.
- Both of the above, but with `consume` replaced by `eat`.
|
|
Prior art:
`rust_analyzer` uses
[`Parser::eat`](https://github.com/rust-analyzer/rust-analyzer/blob/50f4ae798b7c54d417ee88455b87fd0477473150/crates/ra_parser/src/parser.rs#L94), which is `next_if` specialized to
`|y| next_if(|x| x == y)`.
Basically every other parser I've run into in Rust has an equivalent of
Parser::eat; see for example
- [cranelift](https://github.com/bytecodealliance/wasmtime/blob/94190d57244b26baf36629c88104b0ba516510cf/cranelift/reader/src/parser.rs#L498)
- [rcc](https://github.com/jyn514/rcc/blob/a8159c3904a0c950fbba817bf9109023fad69033/src/parse/mod.rs#L231)
- [crunch](https://github.com/Kixiron/crunch-lang/blob/8521874fab8a7d62bfa7dea8bd1da94b63e31be8/crates/crunch-parser/src/parser/mod.rs#L213-L241)
|
|
|
|
`fold` is currently implemented via `try_fold`, but implementing it
directly results in slightly less LLVM IR being generated, speeding up
compilation of some benchmarks.
(And likewise for `rfold`.)
The commit adds `fold` implementations to all the iterators that lack
one but do have a `try_fold` implementation. Most of these just call the
`try_fold` implementation directly.
|
|
|
|
The former `done` flag was roughly similar to an `Option` tag, but left
the possibity of misuse. By using a real `Option`, we can set `None`
when the iterator is exhausted, removing any way to call it again. We
also allow niche layout this way, so the `Fuse` may be smaller.
The `FusedIterator` specialization does want to ignore the possibility
of exhaustion though, so it uses `unsafe { intrinsics::unreachable() }`
to optimize that branch away. The entire `Fuse` implementation is now
isolated in its own module to contain that unsafety.
|
|
r=LukasKalbertodt
Remove `finished` flag from `MapWhile`
This PR removes `finished` flag from `MapWhile` as been proposed in https://github.com/rust-lang/rust/pull/66577#discussion_r370958025.
This also resolves open questions of the tracking issue (#68537):
- `MapWhile` can't implement both
+ `DoubleEndedIterator` (discussed in https://github.com/rust-lang/rust/pull/66577#discussion_r370947990 and following comments)
+ `FusedIterator` (this pr removes `finished` flag, so `MapWhile` isn't fused anymore)
- Debug output (this pr removes `finished` flag, so there is no question in including it in debug output)
r? @Mark-Simulacrum
|
|
Fix bugs in Peekable and Flatten when using non-fused iterators
I fixed a couple of bugs with regard to the `Peekable` and `Flatten`/`FlatMap` iterators when the underlying iterator isn't fused. For testing, I also added a `NonFused` iterator wrapper that panics when `next` or `next_back` is called on an iterator that has returned `None` before, which will hopefully make it easier to spot these mistakes in the future.
### Peekable
`Peekable::next_back` was implemented as
```rust
self.iter.next_back().or_else(|| self.peeked.take().and_then(|x| x))
```
which is incorrect because when the `peeked` field is `Some(None)`, then `None` has already been returned from the inner iterator and what it returns from `next_back` can no longer be relied upon. `test_peekable_non_fused` tests this.
### Flatten
When a `FlattenCompat` instance only has a `backiter` remaining (i.e. `self.frontiter` is `None` and `self.iter` is empty), then `next` will call `self.iter.next()` every time, so the `iter` field needs to be fused. I fixed it by giving it the type `Fuse<I>` instead of `I`, I think this is the only way to fix it. `test_flatten_non_fused_outer` tests this.
Furthermore, previously `FlattenCompat::next` did not set `self.frontiter` to `None` after it returned `None`, which is incorrect when the inner iterator type isn't fused. I just delegated it to `try_fold` because that already handles it correctly. `test_flatten_non_fused_inner` tests this.
r? @scottmcm
|
|
Implement nth, last, and count for iter::Copied
Implement nth, last and count for iter::Copied.
|
|
|
|
|
|
Simplify `Skip::nth` and `Skip::last` implementations
The main improvement is to make `last` no longer recursive.
|
|
|
|
|
|
|
|
|
|
The main improvement is to make `last` no longer recursive.
|
|
The call to `count` on the inner iterator can overflow even if `Skip` itself would return less that `usize::max_value()` items.
|
|
|
|
|
|
|
|
|
|
Override `StepBy::{try_fold, try_rfold}`
Previous PR: https://github.com/rust-lang/rust/pull/51435
The previous PR was closed in favor of https://github.com/rust-lang/rust/pull/51601, which was later reverted. I don't think these implementations will make it harder to specialize `StepBy<Range<_>>` later, so we should be able to land this without any consequences.
This should fix https://github.com/rust-lang/rust/issues/57517 – in my benchmarks `iter` and `iter.step_by(1)` now perform equally well, provided internal iteration is used.
|
|
|
|
Because of a compiler bug that adding `Self: ExactSizeIterator` makes
the compiler forget `Self::Item` is `<I as Iterator>::Item`, we remove
this specialization for now.
|
|
|
|
Override Cycle::try_fold
It's not very pretty, but I believe this is the simplest way to correctly implement `Cycle::try_fold`. The following may seem correct:
```rust
loop {
acc = self.iter.try_fold(acc, &mut f)?;
self.iter = self.orig.clone();
}
```
...but this loops infinitely in case `self.orig` is empty, as opposed to returning `acc`. So we first have to fully iterate `self.orig` to check whether it is empty or not, and before _that_, we have to iterate the remaining elements of `self.iter`.
This should always call `self.orig.clone()` the same amount of times as repeated `next()` calls would.
r? @scottmcm
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Use internal iteration in the Sum and Product impls of Result and Option
This PR adds internal iteration to the `ResultShunt` iterator type underlying the `Sum` and `Product` impls of `Result`. I had to change `ResultShunt` to hold a mutable reference to an error instead, similar to `itertools::ProcessResults`, in order to be able to pass the `ResultShunt` itself by value (which is necessary for internal iteration).
`ResultShunt::process` can unfortunately no longer be an associated function because that would make it generic over the lifetime of the error reference, which wouldn't work, so I turned it into the free function `process_results`.
I removed the `OptionShunt` type and forwarded the `Sum` and `Product` impls of `Option` to their respective impls of `Result` instead, to avoid having to repeat the internal iteration logic.
|
|
Implement DoubleEndedIterator for iter::{StepBy, Peekable, Take}
Now that `DoubleEndedIterator::nth_back` has landed, `StepBy` and `Take` can have an efficient `DoubleEndedIterator` implementation. I don't know if there was any particular reason for `Peekable` not having a `DoubleEndedIterator` implementation, but it's quite trivial and I don't see any drawbacks to having it.
I'm not very happy about the implementation of `Peekable::try_rfold`, but I didn't see another way to only take the value out of `self.peeked` in case `self.iter.try_rfold` didn't exit early.
I only added `Peekable::rfold` (in addition to `try_rfold`) because its `Iterator` implementation has both `fold` and `try_fold` (and for similar reasons I added `Take::try_rfold` but not `Take::rfold`). Do we have any guidelines on whether we want both? If we do want both, maybe we should investigate which iterator adaptors override `try_fold` but not `fold` and add the missing implementations. At the moment I think that it's better to always have iterator adaptors implement both, because some iterators have a simpler `fold` implementation than their `try_fold` implementation.
The tests that I added may not be sufficient because they're all just existing tests where `next`/`nth`/`fold`/`try_fold` are replaced by their DEI counterparts, but I do think all paths are covered. Is there anything in particular that I should probably also test?
|
|
|
|
|
|
|
|
|
|
|
|
DoubleEndedIterators."
This reverts commit 3e86cf36b5114f201868bf459934fe346a76a2d4.
|
|
Add implementations of last in terms of next_back on a bunch of DoubleEndedIterators
Provided a `DoubleEndedIterator` has finite length, `Iterator::last` is equivalent to `DoubleEndedIterator::next_back`. But searching forwards through the iterator when it's unnecessary is obviously not good for performance. I ran into this on one of the collection iterators.
I tried adding appropriate overloads for a bunch of the iterator adapters like filter, map, etc, but I ran into a lot of type inference failures after doing so.
The other interesting case is what to do with `Repeat`. Do we consider it part of the contract that `Iterator::last` will loop forever on it? The docs do say that the iterator will be evaluated until it returns None. This is also relevant for the adapters, it's trivially easy to observe whether a `Map` adapter invoked its closure a zillion times or just once for the last element.
|
