rust-lang
Add infallible variant of RangeFrom::next()
Proposal
Problem statement
RangeFrom is almost a convenient way to count and index things, but its adherence to Iterator makes next fallible, even if there is no actual stop condition (as opposed to full Range, which has a defined endpoint).
This is effectively equivalent to the venerable i++.
Motivating examples or use cases
use std::collections::HashMap;
enum Identifier {
Node,
Listener(String),
}
fn item_labels(node: &str, ids: &[Identifier]) -> HashMap<String, String> {
let mut listener_i = 0..;
ids.iter()
.map(|id| match id {
Identifier::Node => ("node".to_string(), node.to_string()),
Identifier::Listener(listener) => (
format!("listener.{}", listener_i.next().unwrap()),
listener.to_string(),
),
})
.collect()
}
The unwrap is required here to avoid bubbling up the impossible error, but will still set off alarms where panics are forbidden or discouraged (for example, this gets in the way of #[deny(clippy::unwrap_used)]).
Solution sketch
RangeFrom::next()'s implementation is already infallible and can be moved into RangeFrom::advance() (name pending). next() can then be redefined as Some(self.advance()).
Alternatives
Use Iterator::enumerate() (AKA Iterator::zip(0..))
This should be preferred where possible, but doesn't solve cases where you only want to count some subset of values (without filtering out the others entirely).
Increment manually
The same effect can be accomplished by incrementing the integer manually, for example:
fn item_labels(node: &str, ids: &[Identifier]) -> HashMap<String, String> {
let mut listener_i = 0;
ids.iter()
.map(|id| match id {
Identifier::Node => ("node".to_string(), node.to_string()),
Identifier::Listener(listener) => {
let key = format!("listener.{}", listener_i.next().unwrap());
listener_i += 1;
(key, listener.to_string())
}
})
.collect()
}
However, the extra statement feels awkward, and breaks up the otherwise nice expression-oriented code into a read-modify-return sequence.
Publish to crates.io
This would be a possible (if a bit ugly) option, but it would have to wrap the fallible RangeFrom::next() (or reimplement all of the machinery from scratch).
Define an InfiniteIterator trait
Conceptually this makes sense, but it interacts awkwardly with Rust's type system. Ideally, Iterator::next() would be implied by InfiniteIterator::advance(), but that makes combinators impossible to implement neatly.
Links and related work
This is effectively equivalent to the venerable i++ operator.
What happens now?
This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.
Possible responses
The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):
- We think this problem seems worth solving, and the standard library might be the right place to solve it.
- We think that this probably doesn't belong in the standard library.
Second, if there's a concrete solution:
- We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
- We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.
What is it about RangeFrom that it should have this, but other infinite things (say, Repeat) shouldn't? Or would this set a precedent that other things would get the method too?
Personally, my instinct is that if it's worth having, then having a trait for it would be nice, so that Enumerate<Repeat<_>> would also have it, for example.
That said, making a crate to wrap .next().unwrap_unchecked() might also be sufficient.
nit: advance makes me think of the existing advance_by, so I'm not convinced it's a good name.
What is it about RangeFrom that it should have this, but other infinite things (say, Repeat) shouldn't? Or would this set a precedent that other things would get the method too?
IMO Repeat is already covered for this by Clone, so the primary use-case would be in composition.
Personally, my instinct is that if it's worth having, then having a trait for it would be nice, so that Enumerate<Repeat<_>> would also have it, for example.
I'd like to see a trait, but I don't think it's possible in a way that's both clean and correct by construction. There are three obvious ways this could be done:
Implementations
// 1. Independent implementation
trait InfiniteIterator: Iterator {
fn advance(&mut self) -> Self::Item;
}
impl<T: Step> InfiniteIterator for RangeFrom<T> {
fn advance(&mut self) -> Self::Item {
// from existing Iterator::next()
let n = Step::forward(self.start.clone(), 1);
mem::replace(&mut self.start, n)
}
}
impl<T: Step> Iterator for RangeFrom<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
Some(self.advance())
}
}
impl<T, I: InfiniteIterator, F: FnMut(I::Item) -> T> InfiniteIterator for Map<I> {
fn advance(&mut self) -> Self::Item {
(self.f)(self.iter.advance())
}
}
impl<T, I: Iterator, F: FnMut(I::Item) -> T> Iterator for Map<I> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
// existing impl, can't reuse `self::advance()` because it is not always implemented
self.iter.next().map(&mut self.f)
}
}
// 2. Marker trait
trait InfiniteIterator: Iterator {
fn advance(&mut self) -> Self::Item {
self.next().unwrap()
}
}
impl<T: Step> InfiniteIterator for RangeFrom<T> {}
impl<I: InfiniteIterator, F> InfiniteIterator for Map<I, F> {}
// 3. Blanket impl for InfiniteIterator implies Iterator
trait InfiniteIterator {
// Can't reuse Iterator::Item if InfiniteIterator is the source of truth
type Item;
fn advance(&mut self) -> Self::Item;
}
impl<I: InfiniteIterator> Iterator for I {
type Item = <I as InfiniteIterator>::Item;
fn next(&mut self) -> Option<InfiniteIterator> {
Some(self.advance())
}
}
impl<T: Step> InfiniteIterator for RangeFrom<T> {
fn advance(&mut self) -> Self::Item {
// from existing Iterator::next()
let n = Step::forward(self.start.clone(), 1);
mem::replace(&mut self.start, n)
}
}
// causes conflict with the existing `impl Iterator for Map<I>`, which we need for when `I: !InfiniteIterator`
impl<T, I: InfiniteIterator, F: FnMut(I::Item) -> T> InfiniteIterator for Map<I> {
fn advance(&mut self) -> Self::Item {
(self.f)(self.iter.advance())
}
}
I personally don't like any of these. Option 1 leaves the door wide open for implementations to diverge. Option 2 isn't much better than unwrap(), it doesn't guarantee anything by its design. If we want it to be fast and use unwrap_unchecked() then it'd have to be an unsafe trait which just feels wrong. Option 3 makes it completely impossible for a type to be both always an Iterator and selectively an InfiniteOperator.
That said, making a crate to wrap .next().unwrap_unchecked() might also be sufficient.
Yeah.. this comes down to the correct-by-construction question again. In practice I don't see RangeFrom ever violating this, but I'd rather have it be a promise made by RangeFrom itself, rather than an external crate making the promise on its behalf.
nit: advance makes me think of the existing advance_by, so I'm not convinced it's a good name.
Me neither, consider it a placeholder.
Another alternative would be to redefine Iterator as a special case of a generic supertrait, but that makes the compatibility story pretty hairy:
Implementation
#![feature(step_trait)]
use std::{iter::Step, mem, ops::RangeFrom};
trait GenericIterator {
type OptionalItem: MaybeOption;
fn next_generic(&mut self) -> Self::OptionalItem;
// renamed for demonstration purposes, to avoid clashing with std's Iterator
fn map_gen<F>(self, f: F) -> Map<Self, F>
where
Self: Sized,
{
Map { iter: self, f }
}
}
trait MaybeOption {
type Value;
type Map<T>: MaybeOption;
fn map<T, F>(self, f: F) -> Self::Map<T>
where
F: FnOnce(Self::Value) -> T;
fn into_option(self) -> Option<Self::Value>;
}
trait Infinite: MaybeOption {
fn into_value(self) -> Self::Value;
}
impl<T> MaybeOption for Option<T> {
type Value = T;
type Map<U> = Option<U>;
fn map<U, F>(self, f: F) -> Self::Map<U>
where
F: FnOnce(Self::Value) -> U,
{
self.map(f)
}
fn into_option(self) -> Option<Self::Value> {
self
}
}
// identity functor
struct Id<T>(T);
impl<T> MaybeOption for Id<T> {
type Value = T;
type Map<U> = Id<U>;
fn map<U, F>(self, f: F) -> Self::Map<U>
where
F: FnOnce(Self::Value) -> U,
{
Id(f(self.0))
}
fn into_option(self) -> Option<Self::Value> {
Some(self.0)
}
}
impl<T> Infinite for Id<T> {
fn into_value(self) -> Self::Value {
self.0
}
}
type Item<I> = <<I as GenericIterator>::OptionalItem as MaybeOption>::Value;
// Iterator and InfiniteIterator both become special cases
trait InfiniteIterator: GenericIterator {
fn advance(&mut self) -> Item<Self>;
}
impl<I> InfiniteIterator for I
where
I: GenericIterator,
I::OptionalItem: Infinite,
{
fn advance(&mut self) -> Item<Self> {
self.next_generic().into_value()
}
}
trait Iterator: GenericIterator {
// renamed for demonstration purposes, to avoid clashing with std's Iterator
fn next_fin(&mut self) -> Option<Item<Self>>;
}
impl<I> Iterator for I
where
I: GenericIterator,
{
fn next_fin(&mut self) -> Option<Item<Self>> {
self.next_generic().into_option()
}
}
// RangeFrom is always infinite
impl<T: Step> GenericIterator for RangeFrom<T> {
type OptionalItem = Id<T>;
fn next_generic(&mut self) -> Self::OptionalItem {
let n = Step::forward(self.start.clone(), 1);
Id(mem::replace(&mut self.start, n))
}
}
// slices are finite
impl<'a, T> GenericIterator for &'a [T] {
type OptionalItem = Option<&'a T>;
fn next_generic(&mut self) -> Self::OptionalItem {
let item = self.first()?;
*self = &self[1..];
Some(item)
}
}
// Map is generic over finiteness!
struct Map<I, F> {
iter: I,
f: F,
}
impl<T, I, F> GenericIterator for Map<I, F>
where
I: GenericIterator,
F: FnMut(Item<I>) -> T,
{
type OptionalItem = <I::OptionalItem as MaybeOption>::Map<T>;
fn next_generic(&mut self) -> Self::OptionalItem {
self.iter.next_generic().map(&mut self.f)
}
}
fn main() {
let mut infinite = 0..;
assert_eq!(infinite.advance(), 0);
assert_eq!(infinite.advance(), 1);
assert_eq!(infinite.next_fin(), Some(2));
assert_eq!(infinite.map_gen(|i| i + 1).advance(), 4);
let finite = [0, 1, 2, 3];
let mut finite = finite.as_slice();
assert_eq!(finite.next_fin(), Some(&0));
assert_eq!(finite.next_fin(), Some(&1));
// Can't .advance(), not an InfiniteIterator
// finite.advance();
assert_eq!(finite.map_gen(|i| i + 1).next_fin(), Some(3));
}
When we'll have pattern types, and if we'll be able to refine trait methods using pattern types, we will be able to declare fn next(&mut self) -> Option<Self::Item> is Option::Some or whatever syntax it will be.
Pre-RFC on zulip: https://rust-lang.zulipchat.com/#narrow/stream/213817-t-lang/topic/pre-RFC.3A.20pattern.20types/near/387964243
One nice thing about an InfiniteIterator is that it could also enable things like a zip_infinite that wouldn't have some of the optimization/bounds complications that apply to the existing zip.
Such a trait would also open up possibilities like a to-array method that doesn't have to worry about handling the "iterator is too short" cases.