BoundedArray: a simple way to represent small data whose max size is known

[jedisct1]

This is a simple structure containing an array and a length, that can be viewed as a slice.

It is useful to pass-by-copy small data whose whose maximum size is known at comptime but whose exact size is only known at runtime. I found myself using this a lot as it greatly simplifies things over allocators/unions/the-same-thing-done-manually.

Introducing a new type may not be necessary, but it looks like people have been reimplementing something similar in different projects, or resorted to using an Allocator where not really required.

const Key = FixedSlice(u8, 64); // maximum size of a key

fn generateKey(key_len: usize) !Key {
    var key = try Key.init(key_len);
    random.bytes(key.slice());
    return key;
}

FixedSlice is probably not a good name. Suggestions are welcome :)

[LemonBoy]

You can already use a LinearFifo with .static = N size.

[jedisct1]

LinearFifo is a little bit complicated to safely use in a non-fifo context.

New data is concatenated to existing data, update() must be called correctly, there's no symmetry between readableSlice() and writableSlice(), and it will panic on overflow.

In non-fifo contexts, the common practice is to include a buffer and a length for every variable-size member of a structure, and manually set the length and get slices out of these. This is not very convenient especially in public APIs. FixedSlice doesn't do anything more, but offers a reusable interface.

[LemonBoy]

Yeah, using a LinearFifo is definitely suboptimal in public-facing APIs (where the FIFO behaviour is not needed), I brought it up because it's versatile enough

While writing the CPU detection code I needed something like this FixedSlice but with addOne and some other methods, essentially an ArrayList with a fixed amount of backing storage inlined.

What do you think of making this type an ArrayListFixed (name's up for discussion, as always)?

and it will panic on overflow.

I guess this refers to the assert in update.

[jedisct1]

The ability to add an element or a slice may indeed be useful and would be trivial to add.

Are you suggesting that all the methods from ArrayList should be available here?

[LemonBoy]

Are you suggesting that all the methods from ArrayList should be available here?

All the methods that make sense given the fixed capacity, yes.

[jedisct1]

Done.

[tiendung]

I'm writing a text processor in Zig and using similar data struct to FixedSlice or ArrayListFixed quite often to contains chars of words (<30), or words of phrases (<15) ... So +1 for it

[jedisct1]

Used everywhere in https://github.com/jedisct1/zig-hpke too.

[marler8997]

One thought I have here is that this ArrayListFixed differs from ArrayList by a level of indirection. An ArrayList(T) is a reference to data somewhere else, but an ArrayListFixed is itself the data. To me this looks like it could be a footgun because the name ArrayListFixed looks like it could be swapped in for an ArrayList without having to increase the indirection level.

To make this distinction clear, maybe it would be better avoid the name ArrayList? When I look at the implementation, this is really just a wrapper around an "array" but with a field to track a len of sub-elements. So maybe something like PartialArray or ArrayView or ArrayWindow or ArrayBuilder?

EDIT: actually now that I think about it, an ArrayList kinda needs to be passed by reference as well anyway if it's going to mutate, so maybe this is ok?

[jedisct1]

PartialArray or ArrayView or ArrayWindow

All these directly describe something we already have: a slice :)

Damn. Naming things is hard!

[Jarred-Sumner]

All these directly describe something we already have: a slice :)

Maybe a Sliver? A slice of cake has an ambiguous size, but a sliver of cake is small.

Could also call it Smol

[jedisct1]

So, would anybody be strongly against Sliver for that type?

[andrewrk]

I suggest BoundedArray. It communicates that it is an array, which is a by-value type, but with an upper limit on length rather than the length being in the type.

It's interesting that the methods use errors rather than assertions. Everywhere I can think of a use for this type, I would end up using catch unreachable on the methods which return a possible error.

The use case for this type is a bit strange: you have an upper bound on the size needed for the array, but the upper bound is not correct; it can be exceeded depending on runtime conditions.