I was experimenting with const generics and found out that it is not possible to collect an iterator into an array, which is very annoying, when you are working in a no-std environment.
This is my first time writing a (pre-)RFC, so any feedback is greatly appreciated 
(especially spelling and grammar errors)
- Feature Name:
try_from_iterator - Start Date: 2021-04-04
- RFC PR: rust-lang/rfcs#0000
- Rust Issue: rust-lang/rust#0000
Summary
The standard library provides the FromIterator trait, which can be used to construct types from an Iterator, however the construction can not fail. This RFC proposes the addition of the TryFromIterator trait to support these use cases in a standard way.
Motivation
Right now it is not possible to collect an Iterator into a fixed size array.
With the stabilization of const-generics fixed size arrays are used in a lot more places. A lot of times the size of an Iterator is already known, so one could collect into an array instead of a Vec, which requires heap allocations.
For example this iterator:
[1, 2, 3, 4].iter().map(i32::to_string);
only maps its items, so the size does not change, and it is already known beforehand that the size is 4.
Another example is the following:
use core::array;
fn convert_array<T, const N: usize>(array: [Option<T>; N]) -> Option<[T; N]> {
array::IntoIter::new(array)
// remove all None items from the iterator
.flat_map(Option::into_iter)
// try to collect into the array
.try_collect::<[T; N]>()
// if one of the items was None, the array is too large
// -> collecting fails and None is returned
.ok()
}
assert_eq!(convert_array([Some("1"), Some("2"), Some("3")]), Some(["1", "2", "3"]));
assert_eq!(convert_array([Some("1"), None, Some("3")]), None);
assert_eq!(convert_array([Some("1"), None, None]), None);
which maps an array ([T; N]) of Options to Option<[T; N]>.
use core::str::pattern::Pattern;
pub trait StrExt {
fn split_at_most<'a, P, const N: usize>(&'a self, pat: P) -> [Option<&'a str>; N]
where
P: Pattern<'a>;
}
impl StrExt for str {
fn split_at_most<'a, P, const N: usize>(&'a self, pat: P) -> [Option<&'a str>; N]
where
P: Pattern<'a>
{
// NOTE: can be unwrapped, because the error is ! (see below)
self.splitn(N, pat).try_collect().unwrap()
}
}
let string = "255 20 100";
if let [Some(red), Some(green), Some(blue)] = string.split_at_most::<_, 3>(' ') {
println!("red: {}, green: {}, blue: {}", red, green, blue);
} else {
println!("error invalid string");
}
Detailed design
A new trait will be added to the core::iter module:
trait TryFromIterator<A>: Sized {
type Error;
fn try_from_iter<T: IntoIterator<Item = A>>(iter: T) -> Result<Self, Self::Error>;
}
It is similar to TryFrom and From, but for FromIterator.
The Iterator trait will be extended with the following method:
trait Iterator {
type Item;
// ...
fn try_collect<B: TryFromIterator<Self::Item>>(self) -> Result<B, B::Error>
where
Self: Sized,
{
TryFromIterator::try_from_iter(self)
}
}
All types that implement FromIterator should implement TryFromIterator (similar to all types that implement From implement TryFrom)
use core::iter::{FromIterator, IntoIterator};
impl<A, B> TryFromIterator<A> for B
where
B: FromIterator<A>,
{
type Error = !;
fn try_from_iter<T: IntoIterator<Item = A>>(iter: T) -> Result<Self, Self::Error> {
Ok(<Self as FromIterator<T>>::from_iter(iter))
}
}
The following implementation will be added for arrays:
use core::mem::{self, MaybeUninit};
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum CollectArrayError {
NotEnoughItems { missing: usize },
}
impl<A, const N: usize> TryFromIterator<A> for [A; N] {
type Error = CollectArrayError;
fn try_from_iter<T: IntoIterator<Item = A>>(iter: T) -> Result<Self, Self::Error> {
let mut array: [MaybeUninit<A>; N] = MaybeUninit::uninit_array();
let mut iterator = iter.into_iter();
for (i, item) in array.iter_mut().enumerate() {
if let Some(value) = iterator.next() {
*item = MaybeUninit::new(value);
} else {
return Err(CollectArrayError::NotEnoughItems { missing: N - i });
}
}
// One can not simply use mem::transmute, because of this issue:
// https://github.com/rust-lang/rust/issues/61956
let result: [A; N] = unsafe {
// assert that we have exclusive ownership of the array
let pointer: *mut [A; N] = &mut array as *mut _ as *mut [A; N];
let result: [A; N] = pointer.read();
// forget about the old array
mem::forget(array);
result
};
Ok(result)
}
}
Drawbacks
- One might try to use this trait instead of
Result'sFromIteratorimplementation - Might not have enough uses, to justify itself as its own trait.
Rationale and alternatives
-
FromIteratorimplementation for arrays that panics (problematic, because one might want to handle the error case, see theconvert_arrayexample in Motivation) -
One could collect into a structure, instead of adding a new trait:
use core::array;
use core::convert::TryInto;
use core::iter::FromIterator;
use core::mem::{self, MaybeUninit};
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
enum CollectArrayError {
NotEnoughItems { missing: usize },
}
#[derive(Debug, Clone, PartialEq)]
struct ArrayCollector<T, const N: usize>(Result<[T; N], CollectArrayError>);
impl<A, const N: usize> FromIterator<A> for ArrayCollector<A, N> {
fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self {
let mut array: [MaybeUninit<A>; N] = MaybeUninit::uninit_array();
let mut iterator = iter.into_iter();
for (i, item) in array.iter_mut().enumerate() {
if let Some(value) = iterator.next() {
*item = MaybeUninit::new(value);
} else {
return Self(Err(CollectArrayError::NotEnoughItems { missing: N - i }));
}
}
// One can not simply use mem::transmute, because of this issue:
// https://github.com/rust-lang/rust/issues/61956
let result: [A; N] = unsafe {
// assert that we have exclusive ownership of the array
let pointer: *mut [A; N] = &mut array as *mut _ as *mut [A; N];
let result: [A; N] = pointer.read();
// forget about the old array
mem::forget(array);
result
};
Self(Ok(result))
}
}
impl<T, const N: usize> TryInto<[T; N]> for ArrayCollector<T, N> {
type Error = CollectArrayError;
fn try_into(self) -> Result<[T; N], Self::Error> {
self.0
}
}
let iterator = array::IntoIter::new(["1", "2", "3", "4"]);
let result: Result<[_; 4], _> = iterator.collect::<ArrayCollector<&str, 4>>()
.try_into();
println!("result: {:?}", result);
The downside of this solution is that it is quite verbose to use and especially beginners could struggle with it (uses many traits, indirections and type annotations).
Another problem is that it does not allow future extensions with different types (for example one might want to collect into homogeneous tuples).
- The trait could look like this:
trait TryFromIterator<A>: Sized {
type Error;
type StrictError;
fn try_from_iter<T: IntoIterator<Item = A>>(iter: T) -> Result<(Self, T::IntoIter), Self::Error>;
fn try_from_iter_strict<T: IntoIterator<Item = A>>(iter: T) -> Result<Self, Self::StrictError>;
}
where the try_from_iter function returns the Iterator, with the remaining elements and try_from_iter_strict would error if there are remaining elements in the Iterator.
The downside of this solution is that it is unnecessarily complicated. The same can be achieved with the proposed solution, by passing a mutable reference to the try_from_iter function. (there exists an implementation of Iterator for all mutable references to Iterator)
use core::array;
let mut iterator = array::IntoIter::new([1, 2, 3]);
let array: [_; 2] = iterator.by_ref().try_collect()?;
assert_eq!(array, [1, 2]);
assert_eq!(iterator.next(), Some(3));
assert_eq!(iterator.next(), None);
- One could add a blanke impl of FromIterator for Resutl<[T; N], CollectArrayError> instead:
// one can not implement foreign traits on foreign types
#[derive(Clone, PartialEq, Debug)]
pub enum CustomResult<T, E> {
Ok(T),
Err(E),
}
impl<A, const N: usize> FromIterator<A> for CustomResult<[A; N], CollectArrayError> {
fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
let mut array: [MaybeUninit<A>; N] = MaybeUninit::uninit_array();
let mut iterator = iter.into_iter();
for (i, item) in array.iter_mut().enumerate() {
if let Some(value) = iterator.next() {
*item = MaybeUninit::new(value);
} else {
return Self::Err(CollectArrayError::NotEnoughItems { missing: N - i });
}
}
let result: [A; N] = unsafe {
// assert that we have exclusive ownership of the array
let pointer: *mut [A; N] = &mut array as *mut _ as *mut [A; N];
let result: [A; N] = pointer.read();
// forget about the old array
mem::forget(array);
result
};
Self::Ok(result)
}
}
let values: [usize; 6] = [1, 2, 3, 4, 5, 6];
let result = values.iter().map(|v| v + 1).collect::<CustomResult<[usize; 6], CollectArrayError>>();
assert_eq!(CustomResult::Ok([2, 3, 4, 5, 6, 7]), result);
Downside is that it is too verbose, because you have to include the Result and the Error in the annotation.
Prior art
There exist several issues with different implementations:
- Provide a means of turning iterators into fixed-size arrays · Issue #81615 · rust-lang/rust · GitHub
- [Reasoning] A valid const-generic impl Default for arrays, and eventually working to a TryFromIter implementation... · Issue #71514 · rust-lang/rust · GitHub
- Add Iterator::collect_array method by matklad · Pull Request #79659 · rust-lang/rust · GitHub
Posts about this issue:
The arrayvec crate, which provides a fixed capacity ArrayVec, implements FromIterator and panics if there are too many elements in the iterator. (See here)
Unresolved questions
- Implementation for Arrays contains questionable unsafe code (lots of testing would be required)
- should
try_from_iterfail if the array is too small? - Add the following implementation? this could be a
FromIteratorimplementation?
impl<A, const N: usize> TryFromIterator<A> for [Option<A>; N] {
type Error = !;
fn try_from_iter<T: IntoIterator<Item = A>>(iter: T) -> Result<Self, Self::Error> {
let mut array: [MaybeUninit<Option<A>>; N] = MaybeUninit::uninit_array();
let mut iterator = iter.into_iter();
for item in array.iter_mut() {
*item = MaybeUninit::new(iterator.next());
}
let result: [Option<A>; N] = unsafe {
// assert that we have exclusive ownership of the array
let pointer: *mut [Option<A>; N] = &mut array as *mut _ as *mut [Option<A>; N];
let result: [Option<A>; N] = pointer.read();
// forget about the old array
mem::forget(array);
result
};
Ok(result)
}
}
- which traits should be implemented by
CollectArrayError? - how much information should be provided by
CollectArrayError? - are there other types from the standard library, that should implement
TryFromIterator? - Const generics: Generic array transmutes do not work · Issue #61956 · rust-lang/rust · GitHub
- collect into homogeneous tuple?
impl<A> TryFromIterator<A> for (A, A, A) {
type Error = CollectArrayError;
fn try_from_iter<T: IntoIterator<Item = A>>(iter: T) -> Result<Self, Self::Error> {
let mut iterator = iter.into_iter();
Ok((
iterator
.next()
.ok_or(CollectArrayError::NotEnoughItems { missing: 3 })?,
iterator
.next()
.ok_or(CollectArrayError::NotEnoughItems { missing: 2 })?,
iterator
.next()
.ok_or(CollectArrayError::NotEnoughItems { missing: 1 })?,
))
}
}
- because CollectArrayError has only one variant, make it a struct and call it
NotEnoughItemsError?
Future possibilities
In the future one might implement this trait for homogeneous tuples of any size:
if let (a, b, c) = "some example string".split(' ').try_collect::<(&str, &str, &str)>() {
println!("a: {}, b: {}, c: {}", a, b, c);
}
or one could do the following:
// NOTE: syntax might change
// fn split_at_most<'a, P, const N: usize>(&'a self, pat: P) -> (&str, ..Option<&str>)
// where
// P: Pattern<'a>;
if let (a, Some(b), Some(c)) = "some example string".split_at_most::<_, 3>(' ') {
println!("a: {}, b: {}, c: {}", a, b, c);
}
)
