Implement an inline-only growable (bounded) 'vector'

[steveklabnik]

Issue by huonw
Friday Sep 05, 2014 at 01:04 GMT

For earlier discussion, see rust-lang/rust#16998

This issue was labelled with: A-collections, A-libs in the Rust repository

---

Something like [T, .. n] but with a length field (and the correct destructor), so it's valid to store anywhere from 0 upto n Ts in it. This can have Ts dynamically pushed and popped, but attempting to push more than n would be an error. I.e.

let mut x = FourBoundedArray::new(); // n == 4
println!("{}", x); // []
x.push(1);
println!("{}", x); // [1]
x.push(2);
x.push(3);
x.push(4);
println!("{}", x); // [1, 2, 3, 4]
x.pop();
println!("{}", x); // [1, 2, 3]

x.push(5);
x.push(6); // error

(The error could either be fail! or a Result<(), ...> return value.)

This is useful for data structures like 2-4-trees, B-trees etc., where they have internal nodes that store a sequence of keys with variable, but bounded, length. At the moment the only safe way to encode this is either a heap allocation (Vec) or with [Option<T>, .. n] where the "length" is modeled by storing [Some(x_1), Some(x_2), ..., Some(x_length), None, ..., None] (this leads to a lot of unwrap and unnecessary branches).

#197 is related, to make the destructors work right. For full generality we would need integer type params, but we can certainly have an internal abstraction of this form in collections (for use in btree etc.) with the lengths required hard-coded, and generalise/publish it later.

[tdudziak]

I think this could be done in a parameterized way even without integer generics if we use the array type as a parameter. I have a proof-of-concept implementation which seems to work although I'm not completely sure how much I can assume about the low-level representation of [T; n] values.

[bluss]

wow @tdudziak you had the same ideas as I, even down to the name! I've published crates.io/arrayvec by now, and I found some interesting quirks along the way. It turns out Option is not a good idea with uninitialized memory, see testcase here and solution (I think) with this enum here.

Yours is very nice because it doesn't use any array trait at all. That's probably superior.

[nical]

It's worth looking at Gecko's nsAutoTArray: https://hg.mozilla.org/mozilla-central/file/d3228c82badd/xpcom/glue/nsTArray.h#l2296
It has inline storage and reallocates on the heap if the inline capacity is reached. This is extremely useful to be fast those 90% of the time where you know your array will have less than N elements and still works like a regular vector the rest of the time. I am not keen on the idea that the inline growable vector should error when the number of elements exceeds its capacity.

[bluss]

@nical, that's servo's smallvec

[ticki]

Any plans for getting this into the standard library?

[jonas-schievink]

@ticki I hope not until we have proper type-level numerals

[ticki]

Right, that's why I said plans. Having a non-generic one would be a mess.

[WiSaGaN]

smallvec seems to be more of an optimized version of Vec for usages with predominately small size. Imo, this RFC aims for bounded vector that can be layout on stack without any dynamic allocation, at least when the item type is stack based too.
For the return type of push, I have a feeling it may be mostly used in static guaranteed case, where unwrap() every time could be a hassle. If we do use it in a dynamic way, we can always check the size before push. Looks to me panic! is better.
Looking forward for an implementation of this in std.

[ticki]

@WiSaGaN This is not what we are discussing. We are discussing a vector with an arbitrary size, but only heap allocated when a certain length is met.

[WiSaGaN]

@ticki I am not sure that's the case. OP's post explicitly mentioned "bounded".

[bluss]

arrayvec is mentioned in this thread already. It's a bounded capacity vector. Capacity generics are limited by the current state of rust (no integer generic parameters).

[Centril]

Closing this in favor of arrayvec for the time being; const generics are being worked on, rust-lang/rust#44580.