Abstract over dereferenceable containers in Rust

generic_ptr.rs

use std::fmt::Debug;
use std::ops::{Deref, DerefMut};
use std::ptr::NonNull;

trait Ptr {
    type T<'a, U: 'a>: Deref<Target = U>;
}

struct BoxPtr;
impl Ptr for BoxPtr {
    type T<'a, U: 'a> = Box<U>;
}

struct UnsafeNonNull<T>(NonNull<T>);
impl<T: Sized> Deref for UnsafeNonNull<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        unsafe { self.0.as_ref() }
    }
}
impl<T: Sized> DerefMut for UnsafeNonNull<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { self.0.as_mut() }
    }
}

struct NonNullPtr;
impl Ptr for NonNullPtr {
    type T<'a, U: 'a> = UnsafeNonNull<U>;
}

struct RefPtr;
impl Ptr for RefPtr {
    type T<'a, U: 'a> = &'a U;
}

struct Node<'a, T: 'a, P: Ptr + 'a> {
    data: T,
    left: Option<P::T<'a, Node<'a, T, P>>>,
    right: Option<P::T<'a, Node<'a, T, P>>>,
}

impl<'a, T: Debug, P: Ptr> Node<'a, T, P> {
    fn print(&self) {
        println!("{:?}", self.data);
        if let Some(ref left) = self.left {
            left.print();
        }
        if let Some(ref right) = self.right {
            right.print();
        }
    }
}

impl<'a, P: Ptr> Node<'a, i32, P>
where
    P::T<'a, Self>: DerefMut<Target = Self>,
{
    fn incr(&mut self) {
        self.data += 1;
        if let Some(ref mut left) = self.left {
            left.incr();
        }
        if let Some(ref mut right) = self.right {
            right.incr();
        }
    }
}

fn main() {
    let mut node: Node<i32, BoxPtr> = Node {
        data: 0,
        left: None,
        right: Some(Box::new(Node {
            data: 1,
            left: None,
            right: None,
        })),
    };
    node.incr();
    node.print();
    let node: Node<i32, NonNullPtr> = Node {
        data: 2,
        left: None,
        right: None,
    };
    node.print();
    let node: Node<i32, RefPtr> = Node {
        data: 3,
        left: Some(&Node {
            data: 4,
            left: None,
            right: None,
        }),
        right: Some(&Node {
            data: 5,
            left: None,
            right: None,
        }),
    };
    node.print();
}

generic_ptr2.rs

use ghost_cell::{GhostCell, GhostToken};
use slotmap::{SlotMap, new_key_type};
use std::{
    cell::{Cell, RefCell},
    fmt::Debug,
    marker::PhantomData,
    ops::{AddAssign, Deref, DerefMut},
    rc::Rc,
};

trait BorrowSuper {
    type Ref<'a, U: 'a>: Deref<Target = U>;
}
trait Borrow: BorrowSuper {
    type Token;
    type Target;
    fn get<'a>(&'a self, token: &'a Self::Token) -> Self::Ref<'a, Self::Target>;
}

trait BorrowMutSuper {
    type RefMut<'a, U: 'a>: Deref<Target = U> + DerefMut<Target = U>;
}
trait BorrowMut: BorrowMutSuper + Borrow {
    fn get_mut<'a>(&'a self, token: &'a mut Self::Token) -> Self::RefMut<'a, Self::Target>;
}

trait Ptr {
    type T<'a, 'b: 'a, U: 'a>: Borrow<Target = U>;
}

struct Ref<T>(T);
impl<T> BorrowSuper for &Ref<T> {
    type Ref<'a, U: 'a> = &'a U;
}
impl<T> Borrow for &Ref<T> {
    type Token = ();
    type Target = T;
    fn get(&self, _token: &Self::Token) -> &Self::Target {
        &self.0
    }
}

impl<T> BorrowSuper for Box<T> {
    type Ref<'a, U: 'a> = &'a U;
}
impl<T> Borrow for Box<T> {
    type Token = ();
    type Target = T;
    fn get(&self, _token: &Self::Token) -> &Self::Target {
        self
    }
}

struct Wrapper<T>(T);
impl<T> Deref for Wrapper<T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}
impl<T: Copy> BorrowSuper for Cell<T> {
    type Ref<'a, U: 'a> = Wrapper<U>;
}
impl<T: Copy> Borrow for Cell<T> {
    type Token = ();
    type Target = T;
    fn get<'a>(&'a self, _token: &'a Self::Token) -> Self::Ref<'a, Self::Target> {
        Wrapper(Cell::get(self))
    }
}

impl<T> BorrowSuper for &GhostCell<'_, T> {
    type Ref<'a, U: 'a> = &'a U;
}
impl<'brand, T> Borrow for &GhostCell<'brand, T> {
    type Token = GhostToken<'brand>;
    type Target = T;

    fn get<'a>(&'a self, token: &'a Self::Token) -> &'a Self::Target {
        self.borrow(token)
    }
}

impl<T> BorrowMutSuper for &GhostCell<'_, T> {
    type RefMut<'a, U: 'a> = &'a mut U;
}
impl<'brand, T> BorrowMut for &GhostCell<'brand, T> {
    fn get_mut<'a>(&'a self, token: &'a mut Self::Token) -> &'a mut Self::Target {
        self.borrow_mut(token)
    }
}

struct BoxPtr;
impl Ptr for BoxPtr {
    type T<'a, 'b: 'a, U: 'a> = Box<U>;
}

struct RefPtr;
impl Ptr for RefPtr {
    type T<'a, 'b: 'a, U: 'a> = &'a Ref<U>;
}

struct GhostCellPtr;
impl Ptr for GhostCellPtr {
    type T<'a, 'b: 'a, U: 'a> = &'a GhostCell<'b, U>;
}

new_key_type! { struct GraphId; }
struct GraphKey<T> {
    id: GraphId,
    _phantom: PhantomData<T>,
}
impl<T> Clone for GraphKey<T> {
    fn clone(&self) -> Self {
        Self {
            id: self.id,
            _phantom: PhantomData,
        }
    }
}
impl<T> Copy for GraphKey<T> {}
impl<T> From<GraphId> for GraphKey<T> {
    fn from(value: GraphId) -> Self {
        GraphKey {
            id: value,
            _phantom: PhantomData,
        }
    }
}

type GraphMap<T> = SlotMap<GraphId, T>;

impl<T> BorrowSuper for GraphKey<T> {
    type Ref<'a, U: 'a> = &'a U;
}
impl<T> Borrow for GraphKey<T> {
    type Token = GraphMap<T>;
    type Target = T;

    fn get<'a>(&'a self, token: &'a Self::Token) -> &'a Self::Target {
        token.get(self.id).unwrap()
    }
}
impl<T> BorrowMutSuper for GraphKey<T> {
    type RefMut<'a, U: 'a> = &'a mut U;
}
impl<T> BorrowMut for GraphKey<T> {
    fn get_mut<'a>(&'a self, token: &'a mut Self::Token) -> &'a mut Self::Target {
        token.get_mut(self.id).unwrap()
    }
}

struct GraphKeyPtr;
impl Ptr for GraphKeyPtr {
    type T<'a, 'b: 'a, U: 'a> = GraphKey<U>;
}

struct CellRef<'a, T>(std::cell::Ref<'a, T>);
impl<T> Deref for CellRef<'_, T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        self.0.deref()
    }
}
impl<T> Clone for CellRef<'_, T> {
    fn clone(&self) -> Self {
        Self(std::cell::Ref::clone(&self.0))
    }
}
impl<T> BorrowSuper for Rc<RefCell<T>> {
    type Ref<'a, U: 'a> = CellRef<'a, U>;
}
impl<T> Borrow for Rc<RefCell<T>> {
    type Token = ();
    type Target = T;

    fn get<'a>(&'a self, _token: &'a Self::Token) -> Self::Ref<'a, Self::Target> {
        CellRef(self.borrow())
    }
}
impl<T> BorrowMutSuper for Rc<RefCell<T>> {
    type RefMut<'a, U: 'a> = std::cell::RefMut<'a, U>;
}
impl<T> BorrowMut for Rc<RefCell<T>> {
    fn get_mut<'a>(&'a self, _token: &'a mut Self::Token) -> Self::RefMut<'a, Self::Target> {
        self.borrow_mut()
    }
}
struct RcRefCellPtr;
impl Ptr for RcRefCellPtr {
    type T<'a, 'b: 'a, U: 'a> = Rc<RefCell<U>>;
}

struct TreeNode<'a, 'b: 'a, T: 'a, P: Ptr + 'a> {
    data: T,
    left: Option<P::T<'a, 'b, TreeNode<'a, 'b, T, P>>>,
    right: Option<P::T<'a, 'b, TreeNode<'a, 'b, T, P>>>,
}

impl<'a, 'b, T: Debug, P: Ptr> TreeNode<'a, 'b, T, P> {
    fn print(&self, token: &'a <P::T<'a, 'b, Self> as Borrow>::Token) {
        println!("{:?}", self.data);
        if let Some(ref left) = self.left {
            left.get(token).print(token);
        }
        if let Some(ref right) = self.right {
            right.get(token).print(token);
        }
    }
}

struct GraphNode<'a, 'b: 'a, T: 'a, P: Ptr + 'a> {
    data: T,
    edges: Vec<P::T<'a, 'b, GraphNode<'a, 'b, T, P>>>,
}

impl<'a, 'b, T: Copy + AddAssign<T>, P: Ptr> GraphNode<'a, 'b, T, P>
where
    P::T<'a, 'b, Self>: BorrowMut<Target = Self> + Clone,
{
    fn incr(this: P::T<'a, 'b, Self>, token: &mut <P::T<'a, 'b, Self> as Borrow>::Token) {
        let data = this.get(token).data;
        let edges = this.get(token).edges.clone();
        for edge in edges.clone() {
            edge.get_mut(token).data += data;
        }
        for edge in edges {
            Self::incr(edge, token);
        }
    }
}

fn main() {
    let node = TreeNode::<i32, BoxPtr> {
        data: 0,
        left: None,
        right: Some(Box::new(TreeNode {
            data: 1,
            left: None,
            right: None,
        })),
    };
    node.print(&());
    let node = TreeNode::<i32, RefPtr> {
        data: 2,
        left: Some(&Ref(TreeNode {
            data: 4,
            left: None,
            right: None,
        })),
        right: Some(&Ref(TreeNode {
            data: 3,
            left: None,
            right: None,
        })),
    };
    node.print(&());

    // GhostToken usage:
    GhostToken::new(|mut token| {
        let cell1 = GhostCell::new(GraphNode::<i32, GhostCellPtr> {
            data: 1,
            edges: vec![],
        });
        let cell2 = GhostCell::new(GraphNode::<i32, GhostCellPtr> {
            data: 2,
            edges: vec![],
        });
        let cell3 = GhostCell::new(GraphNode::<i32, GhostCellPtr> {
            data: 3,
            edges: vec![],
        });
        cell1.borrow_mut(&mut token).edges.push(&cell2);
        cell2.borrow_mut(&mut token).edges.push(&cell3);

        GraphNode::<_, GhostCellPtr>::incr(&cell1, &mut token);

        println!(
            "{:?} {:?} {:?}",
            cell1.borrow(&token).data,
            cell2.borrow(&token).data,
            cell3.borrow(&token).data
        );
    });

    // Slotmap usage:
    let mut nodes: GraphMap<GraphNode<i32, GraphKeyPtr>> = SlotMap::with_key();
    let node1 = nodes.insert(GraphNode {
        data: 1,
        edges: vec![],
    });
    let node2 = nodes.insert(GraphNode {
        data: 2,
        edges: vec![],
    });
    let node3 = nodes.insert(GraphNode {
        data: 3,
        edges: vec![],
    });
    nodes[node1].edges.push(node2.into());
    nodes[node2].edges.push(node3.into());
    GraphNode::<_, GraphKeyPtr>::incr(node1.into(), &mut nodes);
    println!(
        "{:?} {:?} {:?}",
        nodes[node1].data, nodes[node2].data, nodes[node3].data,
    );

    // Rc Refcell usage:
    let rc1 = Rc::new(RefCell::new(GraphNode::<i32, RcRefCellPtr> {
        data: 1,
        edges: vec![],
    }));
    let rc2 = Rc::new(RefCell::new(GraphNode::<i32, RcRefCellPtr> {
        data: 2,
        edges: vec![],
    }));
    let rc3 = Rc::new(RefCell::new(GraphNode::<i32, RcRefCellPtr> {
        data: 3,
        edges: vec![],
    }));
    rc1.borrow_mut().edges.push(rc2.clone());
    rc2.borrow_mut().edges.push(rc3.clone());
    GraphNode::<_, RcRefCellPtr>::incr(rc1.clone(), &mut ());
    println!(
        "{:?} {:?} {:?}",
        rc1.borrow().data,
        rc2.borrow().data,
        rc3.borrow().data,
    );
}

generic_ptr3.rs

trait NodeOps<T> {
    fn data(&self) -> &T;
    fn left(&self) -> &Option<impl Deref<Target = Self>>;
    fn right(&self) -> &Option<impl Deref<Target = Self>>;
}

fn print_node<T: Debug, Node: NodeOps<T>>(node: &Node) {
    println!("{:?}", node.data());
    if let Some(left) = node.left() {
        print_node(left.deref());
    }
    if let Some(right) = node.right() {
        print_node(right.deref());
    }
}

struct Node<T> {
    data: T,
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
}

impl<T> NodeOps<T> for Node<T> {
    fn data(&self) -> &T {
        &self.data
    }

    fn left(&self) -> &Option<impl Deref<Target = Self>> {
        &self.left
    }

    fn right(&self) -> &Option<impl Deref<Target = Self>> {
        &self.right
    }
}

struct Node2<'a, T> {
    data: T,
    left: Option<&'a Node2<'a, T>>,
    right: Option<&'a Node2<'a, T>>,
}

impl<'a, T> NodeOps<T> for Node2<'a, T> {
    fn data(&self) -> &T {
        &self.data
    }

    fn left(&self) -> &Option<impl Deref<Target = Self>> {
        &self.left
    }

    fn right(&self) -> &Option<impl Deref<Target = Self>> {
        &self.right
    }
}

fn main() {
    let node = Node {
        data: 0,
        left: None,
        right: Some(Box::new(Node {
            data: 1,
            left: None,
            right: None,
        })),
    };
    print_node(&node);
    let node = Node2 {
        data: 0,
        left: None,
        right: Some(&Node2 {
            data: 1,
            left: None,
            right: None,
        }),
    };
    print_node(&node);
}