Struct branded_graph::Graph

#[repr(transparent)]
pub struct Graph<'id> { /* private fields */ }

A branded graph structure with safe and fast self-references.

A Graph can only be obtained as a & or &mut reference via a BrandedGraph by unlock or unlock_mut.

A node is referenced through a NodeRef<'id> index, which is branded with an invariant lifetime, 'id, tied to the Graph that created it. This ensures that references cannot be used with a graph other than the one they were created with. Since nodes can only be pushed (i.e., the length is monotonically increasing), indexing into the graph can safely be unchecked. Graph builds on the BrandedVec technique from “GhostCell: Separating Permissions from Data in Rust” (Yanovski et al., 2021).

In combination, it uses a flat arena structure with indexed references, instead of storing nodes in Rc. For more about flattening graphs, read Adrian Sampson’s explanation of the technique.

Example

A graph is modified within unlock or unlock_mut:

let mut g = BrandedGraph::new();
g.unlock_mut(|g: &mut Graph<'_>| {
    let x = g.push(Node::Number(1));
    let y = g.push(Node::Number(2));
    g.push(Node::Add(x, y));
    println!("{g:#?}");
});

Safety

The API prevents any safety errors and should be sound. However, it has not been proven like in the GhostCell paper. This technique uses lifetimes in an unintended way, so the type errors from violating invariants are not intuitive.

An index may only be used by the graph that created it:

let mut g1 = BrandedGraph::new();
let mut g2 = BrandedGraph::new();
g1.unlock_mut(|g1| {
    g2.unlock_mut(|g2| {
        let x = g1.push(Node::Number(42));
        println!("{}", g1[x]); // ok
        println!("{}", g2[x]); // error
    });
});

Nodes cannot be constructed, that reference nodes from another graph:

// …
        let x = g1.push(Node::Number(1));
        let y = g1.push(Node::Number(2));
        g2.push(Node::Add(x, y)); // error

Graphs cannot be swapped:

// …
        std::mem::replace(&mut g1, g2); // error

Nodes between graphs cannot be compared:

// …
        let x = g1.push(Node::Number(42));
        let y = g2.push(Node::Number(42));
        println!("equal? {}", x == y); // error

The graph, nodes, and node references cannot be smuggled out:

let mut g = BrandedGraph::new();
let node = g.unlock_mut(|g| g.push(Node::Number(42))); // error

These types are all Send + Sync:

assert_impl_all!(BrandedGraph: Send, Sync);
assert_impl_all!(Graph: Send, Sync);
assert_impl_all!(NodeRef: Send, Sync);
assert_impl_all!(Node: Send, Sync);

Implementations

impl<'id> Graph<'id>

pub fn push(&mut self, node: Node<'id>) -> NodeRef<'id>

Push a node and return a reference to it, branded to this graph.

pub fn get_index(&self, index: usize) -> Option<NodeRef<'id>>

Create a branded reference to the node at the given index.

pub fn len(&self) -> usize

pub fn iter(&self) -> impl Iterator<Item = &Node<'id>>

pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut Node<'id>>

pub fn iter_entries(&self) -> impl Iterator<Item = (NodeRef<'id>, &Node<'id>)>

pub fn iter_entries_mut( &mut self ) -> impl Iterator<Item = (NodeRef<'id>, &mut Node<'id>)>

pub fn iter_refs(&self) -> impl Iterator<Item = NodeRef<'id>>

Trait Implementations

impl Debug for Graph<'_>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'id> Index<NodeRef<'id>> for Graph<'id>

type Output = Node<'id>

The returned type after indexing.

fn index(&self, index: NodeRef<'id>) -> &Node<'id>

Performs the indexing (container[index]) operation.

impl<'id> IndexMut<NodeRef<'id>> for Graph<'id>

fn index_mut(&mut self, index: NodeRef<'id>) -> &mut Node<'id>

Performs the mutable indexing (container[index]) operation.

impl<'id> PartialEq<Graph<'id>> for Graph<'id>

fn eq(&self, other: &Graph<'id>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<'id> Eq for Graph<'id>

impl<'id> StructuralEq for Graph<'id>

impl<'id> StructuralPartialEq for Graph<'id>