Github ArrayBuilder struct for safe/efficient dynamic array initialisation by co...

I think we should have a full-fledged ArrayVec instead, though having this as a stop-gap measure that is later deprecated could be a good idea.

conradludgate commented 9 days ago

I think we should have a full-fledged ArrayVec instead, though having this as a stop-gap measure that is later deprecated could be a good idea.

There's already an RFC for that. Mentioned in the Prior Art. I would rather get something smaller scope in quickly so that it can start to be used

burdges commented 9 days ago

There are four ArrayVec-like crates that provide this functionality now, so zero reason for "quickly" doing "stop-gaps". If anything, we need a fifth crate that unifies their various features, ala #2990 (comment) and can thus join std with minimal resistance.

conradludgate commented 9 days ago

I was speaking with @BurntSushi earlier today, he wasn't so sure if it made sense to have such functionality in std just for the sake of it. But array initialisation is one of those basic things that does seem weird to not have.

While they would be similar implementations. I do think the semantics are different.

Thinking of their location too.
ArrayVec makes sense to live in a potential core::collections module
ArrayBuilder makes more sense directly in core::array
IMO

burdges commented 9 days ago

Yes, it's possible they do not unify cleanly, which maybe his concern. I donno..

BurntSushi commented 8 days ago

To clarify my current thoughts:

• Safe array initialization for non-Copy non-const types seems like a primitive we should have, at minimum.
• The need for ArrayVec in std is less clear. I am unsure of how widely used it is. Moreover, given the number of crates that provide ArrayVec implementations, there is a suggestion that the design space for it is large, and that it would perhaps be better for that process to be carried out in the ecosystem. I note that I do not have any special insight into that design space, I am merely making an observation and drawing a tentative conclusion.

conradludgate commented 8 days ago

Safe array initialization for non-Copy non-const types seems like a primitive we should have, at minimum.

Thanks for putting this so succinctly. This is exactly what separates this RFC from the other. Having the minimum needed to enrich core with what should be core functionality.

I personally don't mind if a full ArrayVec makes it's way into std, I have no use for it. But that shouldn't prevent the minimum feature set described above being incorporated first.

kornelski commented 8 days ago •

The ArrayBuilder is pretty much the ArrayVec type: build() could have been try_into(). Giving it a more generic name (not builder) would make the type more useful. It derefs to a slice, so this type is already quite usable as a stack/inline-allocated Vec.

I disagree with @BurntSushi's assessment of ArrayVec. With 20 million downloads, arrayvec is one of the most popular Rust crates. The API is rather simple: it's a Vec. The existing ArrayVec API is fine.

There are multiple crates with seemingly overlapping functionality, because:

1. there's a bunch of forks/alternatives that were created to add const fn and const generics support,
2. there are variants that can seamlessly grow to be heap allocated, or are basically a small vector optimization.

The case 1 is not a problem any more. The case 2 can easily be declared out of scope. There are pros and cons of using the heap for extra growth, but for std — or rather core — it makes sense to focus in the array part more, and have a Copy-compatible nostd-compatible simple type.

ArrayVec solves the initialization problem pretty well. It's more flexible than a callback-based initialization method. Amount of boilerplate code is comparable to MaybeUninit, but safe. When used with a simple loop, it should be a zero-cost abstraction.

I'm not insisting that Rust needs have this type in std/core. Rust already requires 3rd party crates for a lot of basic functionality, and arrayvec works as a crate just fine. But if Rust wanted to have a built-in solution to initializing arrays, adopting arrayvec is a good way to do it. It happens to solve the initialization problem, and is generally useful as an on-stack-Vec too.

BurntSushi commented 8 days ago •

I disagree with @BurntSushi's assessment of ArrayVec. With 20 million downloads, arrayvec is one of the most popular Rust crates.

Just to be clear, I said I was unsure of how widely used it is, not that it isn't widely used. And download count is somewhat deceptive. For example, about 1/3 of arrayvec's downloads come from csv-core, where arrayvec is a dev-dependency. Its total dependents is about 300, which to me says that yeah it's fairly popular. I agree with that. The question is always whether that's enough to to push it over the top and into std.

I'm not insisting that Rust needs have this type in std/core. Rust already requires 3rd party crates for a lot of basic functionality, and arrayvec works as a crate just fine. But if Rust wanted to have a built-in solution to initializing arrays, adopting arrayvec is a good way to do it. It happens to solve the initialization problem, and is generally useful as an on-stack-Vec too.

OK, so I finally had a chance to actually look at this RFC and the API is a lot bigger than what I thought it would be.

When I said "Safe array initialization for non-Copy non-const types seems like a primitive we should have, at minimum." above, what I had in mind was something small and primitive like this: rust-lang/rust#75644

This RFC is a lot more than a simple primitive for building arrays.

Ideally, the primitive would/could be used by the various ArrayVec crates to reduce some unsafe code. So it might be good to get feedback from them on the from_fn API in that PR.

conradludgate commented 7 days ago •

OK, so I finally had a chance to actually look at this RFC and the API is a lot bigger than what I thought it would be.

Ultimately, there's only 3 functions I care about here.

impl<T, const N: usize> ArrayBuilder<T, N> {
    pub fn new() -> Self;
    pub unsafe fn push_unchecked(&mut self, t: T); // UB if array is full
    pub unsafe fn build_unchecked(self) -> [T; N]; // UB if not full
}

With these primitive functions, you can build from_fn quite simply

fn array_from_fn<T, const N: usize>(f: impl FnMut(usize) -> T) -> [T; N] {
    let mut array = ArrayBuilder::<T, N>::new();
    for i in 0..N {
        unsafe { array.push_unchecked(f(i)); } // safe because array won't be full
    }
    unsafe { array.build_unchecked() } // safe because array will be full
}

Similarly, a FromIterator impl is trivial

impl<T, const N: usize> FromIterator<T> for [T; N] {
    fn from_iter<I>(iter: I) -> Self where I: IntoIterator<Item=T> {
        let mut iter = iter.into_iter();
        for _ in 0..N {
            unsafe { array.push_unchecked(iter.next().unwrap()); } // safe because array won't be full
        }
        unsafe { array.build_unchecked() } // safe because array will be full
    }
}

The rest of the functions presented in the RFC are just natural extensions. I'm impartial to the pop functions. I haven't had any use for them, so they can be removed if considered out of scope.

What this ultimately has over just having from_fn built from scratch, is that from_fn is all or nothing. With ArrayBuilder, I can stop half way through, or I can hit an error case, handle it and then extract the initialised values from the Deref slice and clone them into a vec if I were to want them

clarfonthey commented 6 days ago •

I would like to reiterate support for ArrayVec in core over something like this. I wouldn't be opposed to having something like array_from_fn mentioned earlier in addition to an ArrayVec equivalent, but I would be opposed to some ArrayBuilder struct whose functionality wouldn't be extendable to ArrayVec in the future. To be clear, creating some form of ArrayVec while committing only to a very small subset of methods initially would be acceptable imho.

My main justification for ArrayVec is that, IMHO, the use case of "I want between 0 and N elements" is pretty standard, especially with small N. Even something as simple of a 0-2 item array seems extremely reasonable to have on the stack, whereas Vec would add an entire other layer of indirection.

Plus, the ability to have an equivalent to Vec that works in embedded and other no_std environments is a huge plus. I personally use ArrayVec in crates where I know that the upper bound size is small that otherwise would require alloc for such use cases.

Another big thing to point out is that we technically have a cursed equivalent to ArrayVecin libcore in the form of slice::IntoIter, where the use case of a list of 0 to N elements can be covered by a bit of messing around with IntoIter::new.

Plus, there are already a couple things in the compiler itself that should be using some equivalent of ArrayVec but instead use jank enums, like CaseMappingIter

Additional note rereading this: a lot of the time the case where I want "0 to N elements" is in return values, and without unsized rvalues, something like ArrayVec is necessary. IMHO, even with unsized rvalues, I feel like ArrayVec would be better in those cases.