Make key externally constructable

[chrysn]

As this data structure verifies, on access, whether the indicated element is actually allocated (and because keys can outlive their elements anyway -- after all, they are keys and not cursors), it would be convenient to allow a key to be deserialized. Making new public would achieve that, as would a from_index constructor that (unlike new) pre-verifies that the index is within the size range (which might be better than new as it'd allow migration to internal N-dependent size types or even value-limited types as those features become available in Rust).

The particular use case I have in mind for this is the collection pattern of webservers -- it receives a POST, picks a new resource name based on the slots index, and makes that resource accessible until it gets DELETEd. When the client comes back to access or deletes the resource, it passes the key in as a path component.

[chrysn]

I just realized that try_read does exactly that -- kind of. The distinction between key and index is a bit confusing here: Having a key does not guarantee that a read (or modification) will succeed, I'd suggest making that distinction clearer (but don't have any concrete suggestions yet).

[bugadani]

Having a key means having ownership over a particular slot in the data structure. Unless I missed something during implementation, you can only get a key during store and the stored data can only be removed using the key, which consumes the key. This was done on purpose.

[chrysn]

This was done on purpose.

I'm not sure that's even possible, but at least it's not achieved by the keys as they are:

#[test]
fn use_across_slots() {
    let mut a: Slots<u8, U4> = Slots::new();
    let mut b: Slots<u8, U4> = Slots::new();

    let k = a.store(5).expect("There should be room");

    b.take(k);
}

I think that per-array keys would either need to be fat keys (storing a reference to their array) or need some type trickery to ensure there's a different key type for each array -- both would make things a lot harder to use.

[bugadani]

Yes, you are right, this is a known issue and it was not solved because of the exact things you say. I was not concerned by it because in my use case I would only have a few Slots instances, all with different sizes, so the keys wouldn't be interchangeable. I'm not sure how to solve this, but since the intention was to keep the keys functioning more or less like they do now (while making sure they aren't cross-used), I don't think they should be constructable. The goal forward for this lib is to figure out a way to ensure that the keys can't be used in different instances.

[chrysn]

With this design goal, it should be possible to add a try_modify() that allows access by key, but a try_remove would violate that goal as it'll violate the implied promise that using keys never panics.

Removal by key is a crucial component for me, and while I might be able to work around it (eg. by modifying to make it work (by moving the key into the slot after creation), it's far from ideal.

Would you accept changes that allow having either kind of Slots instance (one with guaranteed-to-work keys, one with best-effort keys) provided the overall increase in complexity is small? I think it's possible with the given API.

[bugadani]

The main problem with allowing indices to remove data is that this operation would invalidate keys without any way of notifying the key holder.

I'm open to adding unsafe function(s) to modify items by index, but not to remove them.

[chrysn]

The slots version I'd need would be one where all access is try (or accepting panics because there was just a try_ before); my proposal is to keep those apart on a type base: By default, slots instances would be panic-free unless the fix for #4 is incomplete/circumvented -- but some other slots instances would just use possibly-failing access.

I can't tell whether it makes sense to have both versions in a single crate -- there's sure a lot of implementation that could be shared, but there's a risk of making things overly complex and pushing features to you which you have no use for.

I've published #5 to illustrate what I mean. I'd fully understand if you say this is too complex for a simple crate; if so, I'd look into whether I can maintain a closely related fork with an explained difference and ideally little divergence.

[bugadani]

It's possible to provide a different, more relaxed data structure with your needs in the same crate. For that structure there is no need to define a Key type since it is just an alias over usize.

I admit I still don't quite understand your use case. How do you know the particular piece of data you want to access by indexing is really the one you need?

[chrysn]

My use case is a web server (with a demon on the big web, but the more productive use will be in embedded devices with CoAP). It offers "public" creation of resources whose names are passed back to the client, and which uses those names to access the resource again. A client that attempts to access a resource it has previously deleted does expect that a new one might have been created in the meantime, and assertions on the previous state handled by the server (eg. If-Match headers) further reduce the associated risks.

In some applications, additional mitigation will be provided by:

• allowing some modification (including deletion) only by a client whose credentials match the creating client (they are referenced in the slot item), or
• making the key two-part with an address (for fast access) and a random component or counter (stored in the slot item) to reduce the chances of hitting a newly created resource where one was just deleted; I'd implement that atop of a relaxed-key Slots
• slot items assuming a cooldown state for some time

For some applications (like the online card game I'm using as a demo; also for cases where there's a single-user ACL in place around everything), an unprotected index is good enough, with a two-part key an easy escalation if there is any danger of malicious users guessing IDs. Applications like the Core Resource Directory, unprotected instances would probably only use the cooldown state, while protected instances would use authentication based methods.

[bugadani]

I lost a rather lengthy response due to my browser crashing... The gist of it is:
Slots were made to hand out hardware resources in an embedded environment. For this I absolutely require the ability to restrict modification.
However, in your use case you may be able to hide the Key object in a list associated to your clients' session ids. Basically instead of "work with resource X" you'd do "work with MY 5th resource", while at the same time you could still hand out the key index as a read-only handle. As long as you want private modifications, this would be better than modifying the data structure.

An other solution is to change the collection to a hash map, indexed by 64bit random numbers. This may be better than using Slots because you wouldn't need to use a fixed size collection in an environment with unknown number of clients.

I'm also open to a SlotMap implementation (as detailed here: https://www.youtube.com/watch?v=-8UZhDjgeZU) if it doesn't exist yet. The current Slots idea was somewhat inspired by this talk but it is (apparentally) not a carbon copy. It wouldn't be too hard to implement it and the implementation would fit in the crate as well.

[chrysn]

Session IDs are not something I have available on an embedded web server (eventually this will be used in a CoAP server, and there's not even TCP connections around there), the server pushes every per-client state to the client via the address it passes on to it. The memory limitation of the fixed size array fits the case just as well. ().

A hash map with random indices is what I had considered before, and a heapless version of that (like https://docs.rs/heapless/0.5.4/heapless/struct.IndexMap.html) would do, but why rely on entropy when something slot-like can hand out keys deterministically.

SlotMap sounds pretty much like slots with generation counters tacked on, and would be straightforward to implement based on a no-guarantees version of Slots. (Or, if that makes more sense, on some RawSlots that only deal with fallible access, and atop which both Slots and a SlotMap can be built). If we build a full SlotMap (as I haven't found any; it would have fit the search profile with which I wound up here), I'd probably use it for many applications instead of the Slots – but either way, I think that there's some common usable base.

[chrysn]

Correction: There are SlotMap implementations around (1, 2, 3), but all are dynamic memory backed and thus fell through my search and don't work for my use cases.