Crate ranno

Annotations over recursive data structures.

An Annotation is a type that annotates a child of a recursive data structure with some extra information. Implementing it for a type allows that type to also be an annotation over a reference to a child.

The Annotated type is provided to compute and store the annotation over a reference to a child. Annotations are computed lazily, triggered by when a reference to them is asked for.

Example

extern crate alloc;
use alloc::rc::Rc;

use core::mem;
use ranno::{Annotated, Annotation};

#[derive(Debug, Default, Clone, PartialEq, Eq)]
struct Cardinality(usize);

impl<T> Annotation<LinkedList<T, Cardinality>> for Cardinality {
    fn from_child(list: &LinkedList<T, Cardinality>) -> Self {
        let c = match list {
            LinkedList::Empty => 0,
            LinkedList::Node { next, .. } => 1 + next.anno().0,
        };

        // the cardinality of a linked list is just the cardinality of the
        // next element added to the current one
        Self(c)
    }
}

enum LinkedList<T, A> {
    Empty,
    Node {
        elem: T,
        // the cardinality of a linked list is just the cardinality of the
        // next element added to the current one
        next: Annotated<Rc<LinkedList<T, A>>, A>,
    },
}

impl<T, A> LinkedList<T, A>
where
    A: Annotation<LinkedList<T, A>>,
{
    fn new() -> Self {
        Self::Empty
    }

    fn push(&mut self, elem: T) {
        let mut next = Self::Empty;
        mem::swap(&mut next, self);

        let next = Annotated::new(Rc::new(next));
        *self = Self::Node { elem, next };
    }

    fn pop(&mut self) -> Option<T> {
        let mut node = Self::Empty;
        mem::swap(&mut node, self);

        match node {
            LinkedList::Empty => None,
            LinkedList::Node { elem, next } => {
                let (next, _) = next.split();
                match Rc::try_unwrap(next) {
                    Ok(list) => {
                        *self = list;
                        Some(elem)
                    }
                    Err(next) => {
                        let next = Annotated::new(next);
                        *self = Self::Node { elem, next };
                        None
                    }
                }
            }
        }
    }
}

let mut list = LinkedList::<_, Cardinality>::new();

assert_eq!(Cardinality::from_child(&list), Cardinality(0));

list.push(1);
assert_eq!(Cardinality::from_child(&list), Cardinality(1));

list.push(2);
assert_eq!(Cardinality::from_child(&list), Cardinality(2));

list.pop();
assert_eq!(Cardinality::from_child(&list), Cardinality(1));

Structs

Annotated

A child annotated with some metadata.

AnnotatedRefMut

A mutable reference to an annotated child.

Traits

Annotation

Annotation over a child.