Expand description

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.


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

enum LinkedList<T, A> {
    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>
    A: Annotation<LinkedList<T, A>>,
    fn new() -> Self {

    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;
                    Err(next) => {
                        let next = Annotated::new(next);
                        *self = Self::Node { elem, next };

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

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

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

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

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


A child annotated with some metadata.

A mutable reference to an annotated child.


Annotation over a child.