A ticketing system for storing references to objects that works with the borrow checker in Rust.

theory.md

This design is a thought experiment of mine, which has its origins in the ongoing discussion of the ECS (Entity Component System) design in Rust. The basic idea behind ECS is:

• Entities are owned at the top level, usually by a Vec<T>.
• Indices into the Vec are used to reference a given entity within complex data structures.

This design works really well with Rust's borrow checker, because of the single ownership structure. Since indices alone don't allow read or write access to the data, Rust's borrow checker doesn't consider them aliases. It does have a couple drawbacks:

• If an entity is removed from the Vec without cleaning up all existing index references, then those indices are now stale, and may end up pointing at a different object, breaking application logic (but not causing any UB).
• It's difficult to assert that all index references to a given entity have been removed from nested data structures.
• Slots in the Vec now need to be managed to avoid fragmentation and unbounded growth.
• The design arguably "works around the borrow checker" instead of leveraging its capabilities.

In general, the first point can be mitigated through the use of "generational indices", but the others are still problematic.

As I thought about this problem, I focused on two particular points:

• Indices are just a way to encode a reference to a structure.
• The problem with a direct Rust reference is that it implies some permission to read/write the referenced data, which is why the borrow checker is involved.

My solution is to decouple a direct reference from the ability to access the data it references. This new kind of reference, which I called a Ticket, keeps the referenced data live but cannot be used to access it directly. Instead, access is granted only through a single logical "owner" of the data, which provides an interface to borrow a value (immutably or mutably) given a Ticket for that value. I called this owner a TicketMap. A Ticket is issued by a TicketMap, and branded so that only that TicketMap can be used to manipulate the ticket's value.

Ticket is Clone and internally contains a Rc which tracks how many copies of the Ticket are alive. If the last Ticket referring to a particular value is dropped, then the value itself is dropped. Tickets can also be turned into the TicketMap, which drops them. If the last Ticket for a value is turned in, the value is returned.

This system solves the problems listed above with ECS:

• It's impossible for a Ticket to end up referring to the wrong value.
• It's possible to assert, via TicketMap::turn_in, that no more tickets refer to a given value.
• No management of slots is necessary; the TicketMap doesn't actually store the values in any contiguous or indexable structure.
• The design works with the borrow checker and feels more "Rust-like".

ticket.rs

use std::rc::Rc;
use std::mem;
use std::marker::PhantomData;

#[derive(Clone, Hash, PartialEq, Eq)]
pub struct Ticket<T> {
    // Brand is set by the TicketMap which creates the ticket. It ensures only
    // that TicketMap can ever be used to interact with the ticket.

    brand: u64,
    // Tickets store a pointer to the value they're referencing. Internally it's
    // stored as an option because if the last ticket is turned into the
    // TicketMap it can be converted back to an owned value, leaving the ticket
    // empty. Otherwise, if the last ticket is dropped, it will clean up the
    // memory associated with the value.
    ptr: Option<*mut T>,
    
    // The number of tickets referencing a given value is tracked by this Rc.
    rc: Rc<()>,
}

impl<T> Ticket<T> {
    // Check whether this ticket is the last remaining for a particular pointer.
    pub fn is_last(&self) -> bool {
        Rc::strong_count(&self.rc) == 1
    }
    
    // Consume the ticket and return a pointer to the data.
    fn destroy(mut self) -> *mut T {
        assert!(self.is_last());

        // Set the Option holding the pointer to None and extract the raw
        // pointer in the process.
        let mut ptr: Option<*mut T> = None;
        mem::swap(&mut self.ptr, &mut ptr);
        
        // Return the raw pointer.
        self.ptr.unwrap()
    }
}

impl<T> Drop for Ticket<T> {
    // When a ticket is dropped and it's the last ticket referencing a
    // particular value, the memory holding the value needs to be cleaned up.
    fn drop(&mut self) {
        if !self.is_last() { return; }
        if let Some(ptr) = self.ptr {
            // Convert the pointer back into a managed Box. The Box will then
            // be dropped, causing the memory to be cleaned up.
            unsafe { Box::from_raw(ptr); }
        }
    }
}

static mut global_brand: u64 = 0;

// A TicketMap is the logical owner of data stored within it. It gives out a
// reference for each T stored with it in the form of a Ticket, which can be
// cloned and stored in multiple places. The TicketMap can then be used to
// retrieve borrows of the original value.
struct TicketMap<T> {
    brand: u64,
    _marker: PhantomData<T>,
}

impl<T> TicketMap<T> {
    // Allocate a new TicketMap.
    pub fn new() -> TicketMap<T> {
        unsafe { global_brand = global_brand + 1; }
        TicketMap {
            brand: unsafe { global_brand },
            _marker: PhantomData::default(),
        }
    }

    pub fn store(&mut self, value: T) -> Ticket<T> {
        // Allocate memory to store the value with a Box, and then turn the Box
        // into a raw pointer.
        let ptr: *mut T = Box::into_raw(Box::new(value));
        // At this point, the TicketMap is responsible for managing this memory
        // and ensuring it gets cleaned up.
        Ticket {
            brand: self.brand,
            ptr: Some(ptr),
            rc: Rc::new(()),
        }
    }
    
    // Get a temporary reference to the item referred to by the given ticket.
    pub fn get(&self, ticket: &Ticket<T>) -> &T {
        assert_eq!(self.brand, ticket.brand);
        let ptr = ticket.ptr.unwrap();
        unsafe { &*ptr }
    }
    
    // Get a temporary mutable reference to the item referred to by the given
    // ticket.
    pub fn get_mut(&mut self, ticket: &Ticket<T>) -> &mut T {
        assert_eq!(self.brand, ticket.brand);
        let ptr = ticket.ptr.unwrap();
        unsafe { &mut *ptr }
    }
    
    // Turn in a given ticket, causing it to be dropped. If this ticket is the
    // last remaining reference to a value, return ownership of the value,
    // otherwise return None.
    pub fn turn_in(&mut self, ticket: Ticket<T>) -> Option<T> {
        assert_eq!(self.brand, ticket.brand);
        if ticket.is_last() {
            let b = unsafe { Box::from_raw(ticket.destroy()) };
            return Some(*b);
        } else {
            return None;
        }
    }
}