Collecting iterators into arrays

Changelog
  • Clarify why building [MaybeUninit; N] may not be easy, add link to @scottmcm's lib.
  • Scratched ConstSizeIterator section and added extra comments on extension trait approach.
  • Integrated a first round of feedback and used into_iter for Vec.

Now that const generics are in sight, we may want to think about how we could use them to resolve some long-standing ergonomic issues around arrays in Rust. One, in particular, recently popped up in this github thread: the difficulty of cleanly and efficiently initializing arrays, emerging from to the lack of a way to collect iterators into arrays.

Motivation

As a motivating example, we will use the semi-realistic task of converting a list of borrowed strings into a list of owned strings. If your list is implemented as a Vec, this is trivial...

fn to_owned_vec<'a>(strs: Vec<&'a str>) -> Vec<String> {
    strs.into_iter().map(String::from).collect()
}

...so let's try to do it with arrays. What could possibly go wrong?

fn to_owned_arr<'a>(strs: [&'a str; SIZE]) -> [String; SIZE] {
    /* ??? */
}

Well, first of all, even if we ignore the sad fact that into_iter() does not have the same effect on arrays and Vecs, the obvious conversion from the Vec-based version will not work.

// Won't compile: arrays of T do not implement FromIterator<T>
fn to_owned_arr_fromiter<'a>(strs: [&'a str; SIZE]) -> [String; SIZE] {
    strs.into_iter().map(|&s| String::from(s)).collect()
}

Let's try a loop, maybe, crossing fingers that the compiler will be able to optimize out the unnecessary initial array value?

// Won't compile: Strings are not Copy, so they can't be used in array initializers
fn to_owned_arr_loop<'a>(strs: [&'a str; SIZE]) -> [String; SIZE] {
    let mut a = [String::new(); SIZE];
    for (&inp, out) in strs.iter().zip(a.iter_mut()) {
        *out = inp.to_owned();
    }
    a
}
Future prospects

@Centril pointed out that the future language improvements of rust-lang#49147 would allow this example to work if String::new() were also turned into a const fn.

While this approach would indeed resolve this particular problem among many others, it should be noted that it will not completely resolve the array initialization problem on its own, as some types like File cannot be constructed by a const fn.


Oh well, I just can't get this to work with safe code. Maybe a pinch of unsafe will resolve everything?

fn to_owned_arr_ub<'a>(strs: [&'a str; SIZE]) -> [String; SIZE] {
    let mut a: [String; SIZE] = unsafe { std::mem::uninitialized() };
    for (&inp, out) in strs.iter().zip(a.iter_mut()) {
        *out = String::from(inp);
    }
    a
}

And indeed, this code compiles! But it would be a stretch to say that it works:

  • mem::uninitialized() is deprecated and will go away soon because merely calling it is UB for some types like ! (which can easily accidentally happen in generic code).
    • @RalfJung and @Centril pointed out that String is actually one such type because it features a Unique<u8> member with an "is not null" layout-critical validity invariant. So calling mem::uninitialized() here is actually UB already!
  • &mut to uninitialized memory, as generated by iter_mut(), are instant-UB according to the validity invariants which the Unsafe Code Guidelines are currently proposing.
  • Even if they weren't, overwriting an uninitialized String via an &mut calls its destructor, which is UB.
  • If anything in the loop panicked, we would also be dropping uninitialized Strings, which is still UB.

The correct thing to do, I think, would be to build a [MaybeUninit<String>; SIZE] (which actually may not be so easy until rust-lang#49147 lands), initialize its elements one by one, move everything into a [String; SIZE] at the end, and hope that the compiler manages to optimize everything out. Oh, and maybe add some sort of RAII guard to drop already-initialized Strings when something panics, so as not to leak memory.

I don't know about you, but this is not what I expected a simple array initialization job to look like. I hope this toy example will have convinced you that there is a problem worth fixing here.

So, what should we do?

Implement FromIterator<T> for [T; N]?

This would work perfectly in our example, but it raises the obvious question of what should happen if the iterator ended up producing less than N elements.

As far as I can see, the only thing which this sort of FromIterator implementation can do in this case is to panic, which isn't great because it may break some users' intuition that something called From should not fail (even if this intuition is, strictly speaking, not guaranteed to be respected by FromIterator anyway).

Implement FromIterator<T> for Option<[T; N]> (or similar)?

This provides an ability to handle "bad iterator length" errors, but at the cost of unnecessarily pessimizing the ergonomics in the common case where the length of the iterator is known at compile time by forcing unnecessary unwraps into the code.

It also raises the question of which "bad iterator length" we should catch: just too few elements, or too many elements as well? On this front, @kornel made the case that only "too few elements" errors should be caught and reported because...

  • That is consistent with the existing logic of zip()
  • It makes it easier to deal with infinite iterators.

Personally, I'm convinced by this argument. Which also answers the question of whether one should discriminate between "too few items" and "too little items" by using a Result instead of an Option.

Borrow stackvec's TryFromIterator and try_collect()?

This is a close cousin of the above solution, which would involve a little bit more std changes, but has the advantage of clarifying the faillible nature of collecting an iterator into an array.

It improves upon the previous solution in the following ways:

  • It capitalizes on the existing From/TryFrom distinction
  • try_collect::<[T; N]>() is clearer and easier to type than collect::<Option<[T; N]>>()
  • There is less ambiguity with a possible impl of FromIterator<Option<T>> for Option<[T; N]>

Overall, I think it is a net improvement.

Extend Iterator to communicate compile-time length information?

It seems we could have our cake and eat it too if we could, somehow, only implement FromIterator<T> for [T; N] when the length of the iterator is known at compile-time to be N.

Sadly, it does not seem possible to do this, because although the length of an iterator may be initially known at compile time, and could be kept up to date as adapters are added, the compiler cannot track the length of a partially consumed iterator, and partial iterator consumption is perfectly legal in Rust.

Here's my past attempt at this for reference

Communicating the length of the iterator seems straightforward enough, if tedious. The idea would be to have some sort of ConstSizeIterator: Iterator trait, which exposes the length of an iterator as an associated const if it is known at compile time.

This trait would be implemented by iterators over arrays, and could be implemented for some other constructs too like Ranges with const bounds?

Some iterator adapters like map() would propagate this metadata to their result, while others like filter() wouldn't, silently degrading their ConstSizeIterator into a vanilla Iterator.

But it is not clear to me how this could be integrated into FromIterator, given that the FromIterator trait does not give you a way to specialize implementations based on what kind of iterator you are building the collection from. Probably we would need some kind of FromConstSizeIterator... and it could recurse deeply from there.

Add Iterator-like methods to arrays via an extension trait?

@scottmcm suggested extending arrays with Iterator-like functionality as follows:

Unlike the ConstSizeIterator concept above, this design was successfully implemented. But it does have some unpleasant downsides.

By making "array-map" disjoint from "Iterator-map" and by restricting itself to the Iterator adapters that can safely be implemented on arrays (e.g. no filter() and no flat_map()), I think that this approach risks keeping an large ergonomic gap between array and Vec manipulation. This proposal would make arrays easier to use, but using them would still feel very foreign for someone who's used to the Iterator + Vec workflow.

Further, I would be a bit wary of trusting compilers to optimize the temporary arrays returned by these functions, because I've seen rustc's optimizer struggle in similar areas before. For some reason, lazy iterators seem more readily amenable to its current optimizations than eager collection returns.

Then again, no other workable design for infaillible array construction was proposed so far! So if no one comes up with a better idea, this is the direction that I would propose for this use case.

Your turn!

I've done my best to give a summary of the design space that I've seen so far. Now, can anyone review the description above and tell me if they see any flaw in my reasoning, if there is another way to go about this that I've overlooked, or if they have particular opinions about the proposals above (which are not mutually exclusive)?

cc @est31

3 Likes

I’ve been looking forward to revisiting some of these things:

I picture something like

trait Array {
    type Item;
    const LEN: usize;
    fn map<R>(self, f: impl Fn*(Self::Item) -> R) -> [R; Self::LEN];
    fn generate(f: impl Fn*() -> Self::Item) -> Self;
    // etc
}

so to_owned_arr can just be strs.map(ToOwned::to_owned).

And one can do things like Array::generate(|| x += 1; x) to make arrays.

2 Likes

It is also UB for String, because that contains a NonNull. So the first line of this code is already UB.

2 Likes

For me this leads to the need for a TryFromIterator trait, and an added .try_collect() method (provided, for instance, by an extension trait on Iterators, similar to how .try_into() was added).

This leads to ArrayVec / StackVec, since there is a need to track the number of initialized elements anyways.


I am very much in favor of this direction, since, for a language whose moto is all about zero cost abstractions, having to heap allocate arrays, even when we know that the number of elements is bounded by some constant, is a pitty.

And given how hard it is to properly handle arrays of uninitialized elements (I am pretty sure that the two aforementioned crates are theoretically unsound :confused: ), having it officially provided and supported by ::core becomes almost paramount.

3 Likes

Implementing both ways to collect sounds fine.

  • There will be cases where users map collection of a known size to an array. And if that size turns unexpectedly out too small, then panicking is fine. They’d get a panic too if they collected to a vec and used vec[bad_len].

  • There will be cases where graceful error handling is needed, e.g user may be asked to provide 3 items, but they’ve given 2.

One thing I’m not sure it’s whether collecting into Option or Result won’t be ambiguous compared to Vec which has clever ways to transpose/aggregate options and results from the iterator.

I would always ignore excess elements. For better or worse, .zip already does this. Ignoring may be convenient for chains or infinite length iterators. Otherwise it’d be necessary to add .take(len) and it may be irritating when collect could produce a valid result, just chose not to.

3 Likes

N.B. Tracking issue for RFC 2203, "Constants in array repeat expressions" · Issue #49147 · rust-lang/rust · GitHub, which is probably closer to being fully implemented, will change this such that [const_expr; SIZE]. will work -- However, String::new() isn't a constant expression just yet.

1 Like

Thanks everyone for your feedback so far! I'll try to integrate it into the top post (EDIT: Done).

This design instinctively gets me worried about things like LLVM failing to optimize out the array temporaries or users being puzzled by the ergonomic differences between Array member functions and iterator adapters.

Furthermore, one nice property of the ConstSizeIterator concept, which this design does not replicate, is that it allows you to transparently go from a const-sized iterator to a non-const-sized iterator if you don't really need the const-sizedness property (because you're just going to print out the elements of the iterator for example).

That being said, I also suspect that the notion of const-sized iterators could prove to be a serious rabbit hole in several respects (with ramifications like FromConstSizeIterator or needing to patch many iterator adapters), and from this perspective I count the fact that your design looks much simpler to implement as a strong argument in its favor! So I'll be sure to give it its place as well in the top post!

Are you sure about this? A quick peek through std's source suggests that String is implemented as a Vec<u8>, which is implemented as a RawVec<u8>, whose only nontrivial member is a Unique<u8>, which is a fancy *const u8. I don't see a NonNull here... and don't think there should be one, since String and Vec have a zero-allocation optimization in the empty case...

Not that it changes much, mind you. Even if it happens to work in this case, the fact that mem::uninitialized() breaks in a closely related one ([!; SIZE]) shows that it remains an unpleasantly sharp tool that should only be used with extreme caution.

Nice finding! I like the TryFromIterator design better than that of implementing FromIterator for Option/Result because it feels more consistent with the From terminology and, as @kornel pointed out, implementing FromIterator for Option<[T; N]> might be considered too close to Vec's existing FromIterator black magic.

Are you advocating for StackVec to become a standard library construct here? I agree that one must basically reimplement it in order to initialize an array from an iterator safely, OTOH there is a very strong pressure for the standard library to be as lean as possible and I'm not sure if this struct would meet the "used by sufficiently many people" threshold.

Perhaps std could somehow provide a lowest-common denominator utility between "what is needed to implement TryFromIterator for arrays" and "what is needed to implement a StackVec or ArrayVec"?

@dhm's reference to TryFromIterator helped me frame why I feel uneasy about an implementation of FromIterator that is expected to panic in some cases. As the FromIterator name starts with "From", and there is an expectation from std::convert that something named From must not fail, it seems to me that a panicking FromIterator impl, although compatible with this trait's current contract, might feel too surprising to users.

Which is why I would be interested in a sort of FromIterator that is only implemented when the collection is known to always succeed... Maybe some kind of FromConstSizeIterator?

That all makes sense, thanks for spelling it out!

That's great news! Though I would probably remain slightly worried anytime I see the initialize-with-dummy-value-then-overwrite pattern, as I have observed over time that rustc's (LLVM's?) ability to optimize out such duplicate initialization can be limited in less trivial cases (e.g. initializing diagonal elements of a matrix differently than non-diagonal elements), and then there are the fundamental issues that no compiler will ever be able to optimize out like an array of a type that has a costly Drop implementation...

1 Like

Yep; @RalfJung is right here:

#[rustc_layout_scalar_valid_range_start(1)] // Valid range starts at 1, not 0.
pub struct Unique<T: ?Sized> { ... }

Notably, NonNull<T> has the same attribute applied: non_null.rs - source

3 Likes

Ah, sorry, it's Unique, not NonNull.

Unique has a #[rustc_layout_scalar_valid_range_start(1)], which is the same attribute NonNull uses to become "magic".

The zero-alloc optimization uses a different value that 0 to indicate that there was no allocation (it probably uses cap == 0, so it doesn't even need a special value).

Not only that, even for an uninitialized integer or raw pointers the rules are not set yet -- they might be UB as well. See this UCG discussion.

(And if Discourse would be a better software I wouldn't have had to write all this twice just because my internet connectivity is bad in this train... Seems like it loses your post when the request to save it gets lost. :frowning: )

2 Likes

That's the choice that ArrayVec makes too: ArrayVec in arrayvec - Rust

And it does seem nice for (0..).collect() to be able to give [0, 1, 2, 3, 4].

That seems fundamentally hard, since .next() needs to make the iterator shorter, at which point the const would be wrong. ConstSizeIntoIterator could work; there was a bit of conversation around that in

We have .map() on Option, for example, and such, so I think we have precedent for IntoIterators that have their own versions of some of the iterator things that do more specific things with more specific return types.

And FWIW, a trait like this does work --- I made a macro-implemented version: arraytools - Rust

1 Like

Ah, right, I thought about the adapters but not about the elephant in the room. Silly me :frowning:

Then an array extension trait can only provide an upper bound of the length, which is not useful. So I guess that only leaves TryFromIterator-like APIs and your array methods as our main tracks.

Thanks for writting up such a good summary of the issue!

Rand currently supports generation of up-to-32-element arrays via macros like [_rng.gen::<$t>(), $(_rng.gen::<$ts>()),*]. I think all suggestions here would allow support for arbitrary-length arrays (also without any of these, for types supporting Default).

Array::generate looks like the nicest option, but the above specification is ambiguous:

  1. does this accept any FnMut and always generate elements in order,
  2. or only support Fn (too restrictive for RNGs requiring &mut self),
  3. or only work with function pointers *Fn which can be copied, allowing generation of elements in arbitrary order (and maybe even in parallel)?

Maybe we ought to have generate_mut (or generate_seq aka sequential) as well as generate… though I suspect parallelisation via SIMD or threads may not be possible with this generate prototype anyway (because raw pointers are not Send).

1 Like

For a closer look at what generate() could look like, you may want to check the implementation that @scottmcm linked to: https://docs.rs/arraytools/*/arraytools/ for reference. I forgot to link to it in the OP when I edited it in, my bad. That’s now fixed.

1 Like

Hmmm…

Come to think of it, there might actually be a way to salvage the idea of a ConstSizeIterator. Which I really should have called ConstLenIterator, since “size” can mean something else in Rust and there is prior art for using “len” terminology in an Iterator context. So I will use this latter name in the remainder of this post.

The trick is simple, really: just replace my previous proposal of a ConstLenIterator : Iterator with a ConstLenIterator : IntoIterator.

The semantics then become…

  • A ConstLenIterator can be created from any fixed-size collection, from arrays to a prospective struct ConstLenRange<const FIRST: usize, const LAST: usize>(). Unlike a regular iterator, it is guaranteed to produce a certain number of items N.
  • ConstLenIterator provides a carefully selected set of Iterator-like adapters, such as map() or zip(), that produce other ConstLenIterators. Obviously, those adapters are restricted to the set of Iterator adapters whose output size can be predicted at compile time, e.g. no filter().
  • If you call into_iter() on a ConstLenIterator, you get an Iterator that is guaranteed to produce N elements if iterated immediately without any further fiddling.
  • By doing so, you discard the “constness” of ConstLenIterator and lose its special superpowers, but you gain access to the full Iterator functionality.
  • You may also collect() a ConstLenIterator into a fixed-size collection of the same length (or smaller?). This is trivially implementable using IntoIterator, TryFromIterator and unwrap(), but we can also envision a nicer implementation that guarantees absence of runtime checks through some combination of an UncheckedIterator unsafe abstraction and a generate()-like API.

After some quick experimentation, both const generics and associated consts are much too immature to implement this cleanly today. But given more effort, a hacky macro-based PoC might be workable. Needs more experimenting :slight_smile:

1 Like

Btw, here's a sketch I made a while ago,

1 Like

Nice! I thought about something similar earlier, but was worried about the monomorphization bloat. Do you think it would remain reasonable?

I wouldn't want to speculate. :slight_smile:

Well, after giving it a try, your proposal for a safe constant-length iterator trait cannot be compiled in the current state of the trait system and of the const generics prototype.

In a nutshell, the problem is that if you have a struct TypeBool<const B: bool> and implement a trait T for TypeBool<true> and TypeBool<false>, then the current compiler cannot figure out that T is implemented for all kinds of TypeBool<B>.

EDIT: Reported

1 Like

@Centril: As pointed out elsewhere, the If<T, F, const B: bool> bit can actually be implemented using a dirty specialization trick:

pub struct Bool<const B: bool>;
pub trait Select<T, F> { type Out; }
impl<T, F> Select<T, F> for Bool<{true }> { type Out = T; }
impl<T, F, const B: bool> Select<T, F> for Bool<{B}> { default type Out = F; }
pub type If<T, F, const B: bool> = <Bool<{B}> as Select<T, F>>::Out;

…but it seems the trait system is not able to figure out the subtleties of saturating additions and subtractions, which is somewhat understandable. Basically, this simple test…

pub trait ConstLenIterator<const LEN: usize> {
    /// What kind of items this iterator produces
    type Item;

    /// What will be the type of this iterator on the next iteration (to track
    /// the length, we need to create a new type each time)
    type Next: ConstLenIterator<{LEN.saturating_sub(1)}, Item=Self::Item>;

    /// Produce the next item and iterator
    fn next(self) -> If<(), (Self::Item, Self::Next), {LEN == 0}>;
}

pub struct ConstLenRange<const START: usize, const STOP: usize>;

impl<const START: usize, const STOP: usize>
    ConstLenIterator<{STOP.saturating_sub(START)}> for ConstLenRange<{START}, {STOP}>
{
    type Item = usize;

    type Next = ConstLenRange<{START.saturating_add(1)}, {STOP}>;

    fn next(self) -> If<(), (Self::Item, Self::Next), {START >= STOP}> {
        if START >= STOP {
            ()
        } else {
            (START, Self::Next)
        }
    }
}

…fails to build with this error:

error[E0277]: the trait bound `ConstLenRange<{START.saturating_add(1)}, _: usize>: ConstLenIterator<{LEN.saturating_sub(1)}>` is not satisfied
  --> src/lib.rs:40:5
   |
40 |     ConstLenIterator<{STOP.saturating_sub(START)}> for ConstLenRange<{START}, {STOP}>
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `ConstLenIterator<{LEN.saturating_sub(1)}>` is not implemented for `ConstLenRange<{START.saturating_add(1)}, _: usize>`
   |
   = help: the following implementations were found:
             <ConstLenRange<START, STOP> as ConstLenIterator<{STOP.saturating_sub(START)}>>

…and even if that bit did succeed, I think the next() implementation would be invalid anyway due to the (seemingly) diverging return type. Something like C++'s if constexpr would likely be needed to do this properly.

Looks like the language/compiler duo isn’t ready yet for compile-time-checked constant-size iterators, if you ask me. It’s probably better to go for unchecked (or needlessly-checked) iterators for now.

I think it’s important to be able to make sure that iterator length is equal to array size. This is why I think it will be better to introduce a new method or extension trait:

// names are open to bikeshedding

// This type implements `Try` trait and returns `ArrayCollectError`
// on both non-Ok variants.
enum ArrayCollectResult<T, const N: usize> {
    Ok([T; N]),
    ArrayTooBig,
    ArrayTooSmall([T; N]),
}

enum ArrayCollectError {
    ArrayTooBig,
    ArrayTooSmall([T; N]),
}

impl<T, const N: usize> ArrayCollectResult<T, N> {
    /// Returns an array wrapped in Ok variant, otherwise panics
    fn unwrap(self) -> [T; N] { .. }
    fn expect(self, msg: &str) -> [T; N] { .. }
    /// Returns an array wrapped in Ok and TooSmall variants
    /// and `ArrayCollectError` otherwise
    fn lossy(self) -> Result<[T; N], ArrayCollectError> { .. }
    /// Returns an array only for Ok variant and error otherwise.
    /// Equivalent to using `Try::into_result`.
    fn lossless(self) -> Result<[T; N], ArrayCollectError> { .. }
}

Usage examples:

// note: `collect_array::<N>()` could be replaced with `collect_array(N)`
// in case of introduction of const args
let buf1: [T; 10] = iter1.collect_array()?;
let buf1: [T; 10] = iter1.collect_array().unwrap();
let buf2: [T; 10] = iter2.collect_array().lossy()?;

I think it’s important to make the “lossy” path less comfortable than the “lossless” path.

Alternatively instead of collect_array we could introduce two methods: lossy_collect_array and collect_array. (the latter is “lossless”)

1 Like