A new architecture

[RustyYato]

I was just thinking about how to restructure qcell after #9, and I came up with a way to generalize QCell, TCell, TLCell, and LCell into a single generic type!

The core interface would be:

use core::cell::UnsafeCell;

pub unsafe trait ValueCellOwner: Sized {
    type Proxy;

    fn validate_proxy(&self, proxy: &Self::Proxy) -> bool;

    fn cell<T>(&self, value: T) -> ValueCell<Self, T>;

    fn owns<T: ?Sized>(&self, cell: &ValueCell<Self, T>) -> bool {
        self.validate_proxy(cell.owner_proxy())
    }

    fn ro<'a, T: ?Sized>(&'a self, cell: &'a ValueCell<Self, T>) -> &'a T {
        assert!(self.owns(cell), "You cannot borrow from a `ValueCell` using a different owner!");
        unsafe { &*cell.as_ptr() }
    }

    fn rw<'a, T: ?Sized>(&'a mut self, cell: &'a ValueCell<Self, T>) -> &'a mut T {
        assert!(self.owns(cell), "You cannot borrow from a `ValueCell` using a different owner!");
        unsafe { &mut *cell.as_ptr() }
    }

    fn rw2<'a, T: ?Sized, U: ?Sized>(
        &'a mut self,
        c1: &'a ValueCell<Self, T>,
        c2: &'a ValueCell<Self, U>,
    ) -> (&'a mut T, &'a mut U) {
        assert!(self.owns(c1), "You cannot borrow from a `ValueCell` using a different owner!");
        assert!(self.owns(c2), "You cannot borrow from a `ValueCell` using a different owner!");
        assert_ne!(c1 as *const _ as usize, c2 as *const _ as usize, "You cannot uniquely borrow the same cell multiple times");
        unsafe { (&mut *c1.as_ptr(), &mut *c2.as_ptr()) }
    }
}

pub struct ValueCell<Owner: ValueCellOwner, T: ?Sized> {
    owner: Owner::Proxy,
    value: UnsafeCell<T>
}

impl<Owner, T> ValueCell<Owner, T>
where
    Owner: ValueCellOwner
{
    pub fn from_proxy(owner: Owner::Proxy, value: T) -> Self {
        Self { owner, value }
    }
}

impl<Owner, T: ?Sized> ValueCell<Owner, T>
where
    Owner: ValueCellOwner
{
    pub const fn as_ptr(&self) -> *mut T {
         self.value.get()
    }

    pub const fn owner_proxy(&self) -> &Owner::Proxy {
         &self.owner
    }
}

All of the current types could be modeled like so,

type QCell<T> = ValueCell<RuntimeOwner, T>;

struct RuntimeOwner {
    id: u32
}

struct RuntimeProxy(u32);

unsafe impl ValueCellOwner for RuntimeOwner {
    type Proxy = RuntimeProxy;

    fn validate_proxy(&self, proxy: &Self::Proxy) -> bool {
        self.id == proxy.0
    }

    fn cell<T>(&self, value: T) -> ValueCell<Self, T> {
        ValueCell::from_proxy(RuntimeProxy(self.id), value)
    }
}

[RustyYato]

The advantages to the new architecture:

• the unsafe is simpler to check
• it is easier to support no_std.
• this is extensible
• users can easily swap implementations, and be generic about implementations

[RustyYato]

I started working on this in #12

[uazu]

I think possibly I take advantage of the unique features of each ownership type in some places. For example, QCell has a QCellOwnerID, so it doesn't need to have direct access to the owner to create a cell. This happens to be useful when the borrow checker makes it hard to get references to everything you need all at once. For the other types, there is no need at all for the owner to be accessible to create a cell. Also, I'm not totally sure how things are going to work out with the lifetimes and marker types with this approach. I found the ways that worked well mostly in the traditional Rust style of trying all the things that didn't work first! I can't say for sure how this approach will work out, so I think I'll just wait to see how you get on with it.

[RustyYato]

I think possibly I take advantage of the unique features of each ownership type in some places. For example, QCell has a QCellOwnerID, so it doesn't need to have direct access to the owner to create a cell. [...] This happens to be useful when the borrow checker makes it hard to get references to everything you need all at once.

We can create wrapper functions that put this functionality back, this is just swapping out the core. Nothing I have proposed here should break any existing code.

I have now created a working prototype, look in the *_impl.rs files for the implementations.

[uazu]

Okay, I'm getting my head around this. I see the idea now. A few comments:

I find the term "proxy" confusing. I know (now) that this is a type containing/embodying a proxy for the ownership, i.e. the integer, marker type or lifetime, but "proxy" on its own in the source doesn't make a lot of sense. Perhaps "marker" would work better.

You've lost the free list for IDs for QCell. That was important. Imagine the case where a function allocates an owner for temporary working storage of cells whilst processing and then frees everything up and releases the owner before returning. With the current implementation you've limited the use of this function to 2^32 calls. (I originally had the fast_new() call as new(), because the risk of unsafe use is zero in practice assuming the coder doesn't actively want to create bugs, but as someone on the forum pointed out, it could be abused maliciously to cause unsound behaviour without unsafe. So I had to add the current free list implementation to not lose functionality.)

You've renamed a lot of stuff internally, e.g. SingletonOwner, but it looks like this leaks out to the crate user, e.g. in panic messages. So assuming we stick to the current naming in the public interface, that will cause confusion. It would be better to keep naming consistent, even if perhaps you'd prefer your naming.

I think I'm mostly okay with this approach. It does bring common things together in the code without adding too much type machinery to achieve it. However, there's a downside in that it complicates things for the crate user because I think probably they'll be seeing ValueCell in arguments and compiler messages instead of the cell type they were expecting, but assuming the marker types are named in a recognisable way, that should probably still be understandable enough. I'll need to look at how many internal types are getting exposed in the API now, though, because I'd prefer the exposed API to be minimal. Really totally minimal would be my preference, but that's probably not going to be possible with this approach. I will think some more tomorrow.

[RustyYato]

I find the term "proxy" confusing. I know (now) that this is a type containing/embodying a proxy for the ownership, i.e. the integer, marker type or lifetime, but "proxy" on its own in the source doesn't make a lot of sense. Perhaps "marker" would work better.

That's fine, I'm not too concerned about nomenclature

You've lost the free list for IDs for QCell. That was important. Imagine the case where a function allocates an owner for temporary working storage of cells whilst processing and then frees everything up and releases the owner before returning. With the current implementation you've limited the use of this function to 2^32 calls.

We could easily increase the size to u64, or even just a 48-bit number which would basically make this problem go away. Even if we just went with a 48-bit number, generating 1000 QCellOwners per second continuously would not exhaust all possible ids for 9k years. I think that is far longer than we is reasonable to worry about.

This new method has two benefits, it is now significantly cheaper to create a QCellOwner (just 1 relaxed atomic load and 1 relaxed compare exchange in the happy path), and it makes safe QCell no_std compatible. The speed benefits are so great, that I don't think that we need a fast_new because it doesn't significantly improve performance.

(I originally had the fast_new() call as new(), because the risk of unsafe use is zero in practice assuming the coder doesn't actively want to create bugs, but as someone on the forum pointed out, it could be abused maliciously to cause unsound behaviour without unsafe. So I had to add the current free list implementation to not lose functionality.)

Yes I remember commenting on that in users a while back

You've renamed a lot of stuff internally, e.g. SingletonOwner, but it looks like this leaks out to the crate user, e.g. in panic messages. So assuming we stick to the current naming in the public interface, that will cause confusion. It would be better to keep naming consistent, even if perhaps you'd prefer your naming.

Yes, I will rename things back, I had some of this implementation work from some previous project based on an earlier version of this crate that I unearthed and adapted for qcell. :)

I think probably they'll be seeing ValueCell in arguments and compiler messages instead of the cell type they were expecting, but assuming the marker types are named in a recognisable way

Yes, they will see ValueCell in error messages, but I think this should be fine, for example they would see ValueCell<QCellOwner, _> and they could see that this is a QCell. This is the problem with making things more generic, unfortunately.

I'll need to look at how many internal types are getting exposed in the API now, though, because I'd prefer the exposed API to be minimal. Really totally minimal would be my preference, but that's probably not going to be possible with this approach. I will think some more tomorrow.

I think right now there are only 2 types per type of cell that get exposed. The Owner (already exposed) and a Marker (previously Proxy, this one is new for TCell, TLCell, and LCell, for QCell this is just the same as QCellOwnerID). There is also the generic ValueCell type, which is already exposed.

[uazu]

It's unfortunate that giving the code a major overhaul like this means going through the whole thing once again with a fine-toothed comb looking for subtle bugs and issues. I have another crate I was hoping to get finished before the new year. I'll have to balance my time.

I didn't want a u64 ID because I wanted it to be lean in memory. All the cells have to carry this data. Creation of owners shouldn't be the main bottle-neck. Creation of cells will dominate. In my mind the memory cost outweighs the cost of owner creation, assuming packing and alignment issues don't sabotage that. (I'm imagining use on 32-bit processors as well, e.g. embedded.) I think anyone who cares about speed of owner creation should be using fast_new(). So the slower free-list code is only for those who value no-unsafe over speed, or who are creating just few owners. Going lower, e.g. to u16 doesn't buy us much. So u32 is about right, but can't be guaranteed to cover all owners over the lifetime of a process in some use-patterns. Anyway, this is how I ended up with the present implementation to balance the concerns. This isn't theoretical BTW -- this is going into a product soon.

It occurred to me that if your objection to the original code was the code duplication, perhaps that could be worked around with a macro to generate the common code. This could use the same Proxy/Marker approach you've introduced, but would generate the code in place, so wouldn't expose any new types. This would end up neater for the user.

However, alternatively maybe we could "pivot" the whole concept of the crate and embrace the ValueCell as the main type (maybe call it something else), but that's an even bigger change, considering the doc rewrites and so on. Even so, the generic approach does remain more verbose, and potentially confusing to the user where there are type aliases.

I will respond more fully to the other points in the morning.

[RustyYato]

I didn't want a u64 ID because I wanted it to be lean in memory. All the cells have to carry this data. Creation of owners shouldn't be the main bottle-neck. Creation of cells will dominate. In my mind the memory cost outweighs the cost of owner creation, assuming packing and alignment issues don't sabotage that. (I'm imagining use on 32-bit processors as well, e.g. embedded.)

I currently implemented a 48-bit ID. I can roll that back quite easily, but I think this is a good default for a general use case. I am thinking beyond just a single project, what if we have multiple crates using this. They shouldn't run out of IDs just because we have a lot of crates. With 48-bit IDs that is extremely unlikely to happen, but it is possible with 32-bit IDs.

Your memory argument rings hollow for me. If you really care about the difference of a handful of bytes, then you really shouldn't be using QCell. You should use any of the other ones that don't have a memory overhead. It is far more important to have a safe api, that is just as fast. At the end I show a way that we can extend this rewrite in the future to make this concern even less of an issue.

Most importantly, I don't like advertising unsafe as something to casually use. This cheapens the meaning of unsafe and makes it harder to build reliable unsafe apis when people don't care about the ramifications of unsafe.

Also, your comment about short-lived owners,

That was important. Imagine the case where a function allocates an owner for temporary working storage of cells whilst processing and then frees everything up and releases the owner before returning.

This is a perfect use-case for LCell, not QCell. By making this library more generic, we can allow people to build their data structures generically, and choose which implementation they need differently in different parts of their codebade. QCell here, LCell there.

Anyway, this is how I ended up with the present implementation to balance the concerns. This isn't theoretical BTW -- this is going into a product soon.

This implementation that I am proposing is not theoretical either. It is heavily inspired by lock_api, the core of parking_lot.

Even so, the generic approach does remain more verbose, and potentially confusing to the user where there are type aliases.

I don't think that this is a large concern, as the very first generic parameter will tell exactly what type they are dealing with.

It occurred to me that if your objection to the original code was the code duplication, perhaps that could be worked around with a macro to generate the common code.

Macros tend to be harder to audit than types, so I'm a but wary of making anything but the most simple unsafe implementations in macros. Also, I have some ideas for the future that are based on this interface (see below)

This could use the same Proxy/Marker approach you've introduced, but would generate the code in place, so wouldn't expose any new types. This would end up neater for the user.

Note, we can hide all marker marker types from the user except for QCell, and have the same api as before. There could be no mention of TCellMarker anywhere in the docs, except in the implementation of ValueCellOwner (which users shouldn't care too much about).

---

Another beneift to this approach, if users want to build their own version of say, QCell that is smaller then they only need to implement a single unsafe trait that will have a clear and simpler requirements. They won't have to prove a correct implementation of rw3, they get that for free.

This could be encouraged by way of a proc-macro, allowing people to do this in safe code:

#[derive(ValueCellOwner)]
#[vco="runtime"]
struct RuntimeOwner(u8);

That way they can cater specifically to their needs.

In the future, we can make TCell safe on no_std using macros, but that can be done after the rewrite. The idea is based on how closures are always a new type.

[RustyYato]

Thinking about this some more, another possibility is to make QCell itself more generic. (Although this might be going overboard). Here is a sketch on playground

[uazu]

Right, I went offline for a bit to try some different things and to think. There are still a number of problems:

48-bits is the same as 64-bit because of alignment and packing issues. So there's only really a choice between u32 and u64. See playground. usize might also be an option, because u32 is probably going to be forced to fill a usize slot if the embedded structure has any pointers in it, but that doesn't help us at all on 32-bit platforms, where a usize will still potentially run out. So I think the two choices remain exactly as they were before: either re-use IDs or get the caller to indicate unsafe and promise not to abuse the API by attempting to cause ID clashes.

It's not true that someone using QCell and being sensitive about the memory cost could just switch to one of the other cell types. You clearly have not tried this in real life. LCell is very very verbose to use. It means lifetime annotations on all the structures affected and through all the functions that pass the 'ownership' up the stack. To me it is unusable for my current project. Maybe in a few niche applications it will really shine, but I can't use it. TCell and TLCell have the limitation that there can only ever be one owner per marker type. So you can't create two of whatever it is that contains the owner. If you do want to do that, you need QCell. So there are cases where there is no choice but to use QCell.

Regarding leaking internal types, the question is "How to teach this?". The competition is RefCell which is really straightforward. QCell at present is almost as straightforward, but if we're using type aliases then types are going to leak out, and we have to teach the user that if they see this weird internal type, then really it means QCell. For users of the basic 4 types, all the generic stuff is internal implementation details that only complicate things for them. Okay, if they want to make a QCell with a different size, then it is useful. But just for that! Nothing else. It shouldn't be exposed in the public interface for the basic types.

I don't see how you are hoping to hide the types. Yes, you could make the 4 cell types be wrappers around the Value* types, but that is going to be even more verbose than the current implementation.

What I like from your PR is the unification through the Proxy/Marker types. That I may end up borrowing from you at some point, if I can think of a way to do it cleanly.

I wondered whether the unification would help in my current project, where I do need to switch between QCell/TCell/TLCell according to features. However actually it didn't help at all. All I require in that case is that the API is the same, or close enough.

Interestingly I wanted to also offer a fully-safe option using RefCell (in case anyone doesn't trust qcell), but RefCell can't be persuaded to work through a compatible API, because it doesn't return references directly, just Ref or RefMut temporary objects.

You code incredibly quickly and obviously all this higher type stuff and higher macro stuff is obvious and easy for you. However, if I put some of that code in front of most people in the Rust community they would run in fear.

I work as a software engineer and I have to write clear code and ship solid products. At little bit of code duplication is manageable, as in this crate. I have to worry about how people who do not understand Rust that well will cope with whatever error messages come up as they try to get things working. I have to keep the conceptual burden and complexity level down, or else I will end up having to solve the problem for them. I also have to be concerned about company in-house unsafe reviewers, who probably are not genius-level. Complex approaches have to really bring a large payoff to be worth it.

So, I think the downsides of the approach in this PR are still outweighing the advantages.

[RustyYato]

48-bits is the same as 64-bit because of alignment and packing issues.

Nope, it is stored as [u8; 6], so it has 1 byte alignment. It will be packed.

It's not true that someone using QCell and being sensitive about the memory cost could just switch to one of the other cell types. You clearly have not tried this in real life. LCell is very very verbose to use. It means lifetime annotations on all the structures affected and through all the functions that pass the 'ownership' up the stack. To me it is unusable for my current project.

Ok, I didn't think that through too much. But I think the other method of making it easy to create your own version of QCell should solve this nice enough.

You code incredibly quickly and obviously all this higher type stuff and higher macro stuff is obvious and easy for you. However, if I put some of that code in front of most people in the Rust community they would run in fear.

I'm not so sure about this, given that these sorts of type tricks are the same as the ones in parking_lot, which has 328 reverse dependencies on crates.io, and millions of downloads. So clearly, using similar type tricks isn't an issue. Similarly for macro, yes implementing these macros may be difficult, but using them is easy, so I don't think people would run from them.

I work as a software engineer and I have to write clear code and ship solid products. At little bit of code duplication is manageable, as in this crate. I have to worry about how people who do not understand Rust that well will cope with whatever error messages come up as they try to get things working.

That's understandable, I know I have a tendency to over complicate things, so if this is going too far that's fine. Error messages with generic types are a mess right now, and it would be nice if Rust used type aliases in error messages where they are used in source to make this manageable.

I don't see how you are hoping to hide the types. Yes, you could make the 4 cell types be wrappers around the Value* types, but that is going to be even more verbose than the current implementation.

I think the thing that differs the most between us is the focus on error messages. If you value readable error messages over reducing code duplication then I think you should stick to the current framework.

But I still strongly suggest that you at least switch to using 48-bit IDs for QCell. You can store them in a [u8; 6] and this will keep the alignment down, and only add 2 bytes to the ID (rounding up to alignment of larger types, which should be negligible). This will make QCellOwner entirely safe without sacrificing fast_new's performance.

---

Thanks for your feedback!

[RustyYato]

Would making QCell just 1 step more generic to allow for custom IDs be a satisfactory compromise? That way by default, you can have 48-bit IDs that are safe and will work for basically every use case, but if you need to, you can drop down to a smaller size ID for size critical parts.

This won't affect the error messages in a meaningful way, but it will make it easier to isolate each libraries usage of QCell, so that they don't interfere with each other.

[uazu]

Whilst [u8; 6] has 1-byte alignment, when combined with something else that doesn't have 1-byte alignment, it ends up getting rounded up. It can't even use the spare space at the end of another structure (see the playground link above). Whilst I think Rust made a mistake to handle things this way, this is what we have to live with. Really Rust should know three things for each type: alignment, copy-size (unrounded) and stride-size (for arrays). Then it could use free space at the end of structures for enum discriminants and for packing a surrounding structure better (as in this case). But anyway right now using a 48-bit ID with anything with 4- or 8-byte alignment takes the same memory as using a 64-bit ID. So essentially the choice is still between u32 and u64.

I like the unification in this PR, but I don't like the way it leaks out into the user experience and public API. Let's leave things as they are at the moment. With experience perhaps some other reason to adopt this approach will become clear and I'll come back to it. Thanks.

[RustyYato]

Ok that makes sense. In that case can I make a PR to make the ID pluggable. That way different libraries can use their own IDs if they want. You can keep the default to 32-bit with ID reuse, but this allows it others to craft their owns IDs. This would also make it slightly easier to implement no_std support, you would just need to change the default from reuse 32-bit, to no reuse 32-bit (which could be different types).