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

[huonw]

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).

rust-lang/rfcs#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.

[Gankra]

I think this is sort of a dupe of #16522

Agreed on all points, though.

[Kimundi]

The full general form (rust-lang/rfcs#197 + integer in type system) would also be a solution to the problem of initializing a [T, ..N] incrementally, as you could just build up a fixed capacity vector and then unwrap it.

[huonw]

I think this is sort of a dupe of #16522

Yeah, definitely related, but not quite a dupe, that SmallVec:

• is unbounded, as it promotes to heap allocation beyond the limit;
• is larger than necessary for this (the ptr and capacity words are unnecessary... even a uint length is unnecessary in many circumstances, I'm sure n < 256 in most cases, and length: u8 works there)
• does unnecessary work (branching to decide on inline vs. heap when indexing etc.)
• reduces use-cases, this one can be used in environments without allocation.

(And as @Kimundi points out, this could be used as a low-overhead way to initialise fixed length arrays.)

[Gankra]

👍 Yep, this would be way simpler than smallvec. Definitely needs integer type params, though. iirc there's a couple closed RFCs for this (can't for the life of me find them now).

@huonw Would you be interested in working on an RFC for this? (post 1.0, presumably)

[huonw]

Definitely needs integer type params

Only for the generic version; if this is needed/really wanted now, we can take the same approach as servo's smallvec and just hardcode the sizes required (e.g. have a macro that creates them).

(This is what my last paragraph refers to. :) )

Would you be interested in working on an RFC for this? (post 1.0, presumably)

Not at the moment, sorry.

[Gankra]

hardcoded sizes make me sad 😢 (especially since BTree itself just wants this)

[huonw]

The BTree only needs a generic version of this type if the BTree is generic over integer types itself, and clearly if the latter happens we will be able to generalise this, so non-hardcoded sizes are an independent issue (at least, if this is an internal 'implementation detail'/#[experimental] item inside collections).

[Gankra]

Yes, sorry. I was simply referring to the fact that ideally B should be configurable in some static fashion.

[nikomatsakis]

So, it seems like default type parameters mean that we could go forward with a fixed-size variant and then seamlessly make it extensible in the future.

[Gankra]

@nikomatsakis Not if we're providing a family of structs like InlineVec1, InlineVec2, InlineVec4, ...

However if this is just a purely internal thing, I suppose it could just be tailored to whatever BTree wants, and we can call it a day.

[nikomatsakis]

On Fri, Sep 05, 2014 at 08:10:06AM -0700, Alexis Beingessner wrote:

@nikomatsakis Not if we're providing a family of methods like InlineVec1, InlineVec2, InlineVec4, ...

Why not? Those wind up as aliases to InlineVec<1>, InlineVec<2>
etc. But I confess I was thinking that we just make InlineVec, tie it
N=32 or whaever we want, and then start working on an RFC for integer
generics to appear ASAP after 1.0 :)

[Kimundi]

Hm, that also sounds like a reasonable approach, though pinpointing the exact default number of elements we want might be hard to do up front :)

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#863