Messing around with linear types to implement cyclic structures

halfbox.rs

// API for half-boxes
// These are like boxes, but when you create them, you get two of them,
// and you can get a box back by calling half1.whole(half2).
// It's a run-time error if you ever call  half1.whole(half2) for half-boxes
// which weren't created as a pair.

trait Extractable {}
impl<T> Extractable for Option<T> where T: Extractable {}
impl<T> Extractable for HalfBox<T> {}
impl Extractable for u64 {}

struct HalfBox<T> {
    ptr: *mut T, // CLAXON! CLAXON! CLAXON!
}

impl<T> HalfBox<T> {
    fn new(value: T) -> (HalfBox<T>, HalfBox<T>) {
        let ptr = Box::into_raw(Box::new(value));
        (HalfBox{ ptr: ptr }, HalfBox{ ptr: ptr })
    }
    #[allow(unused_mut)] 
    fn whole(mut self, mut other: HalfBox<T>) -> Box<T> {
        if self.ptr != other.ptr { panic!("Making a whole from different halves.") }
        let result = unsafe { Box::from_raw(self.ptr) };
        std::mem::forget(self);
        std::mem::forget(other);
        result
    }
}

impl<T> HalfBox<T> {
    fn extract<F,U>(&mut self, f: F) -> &mut U
        where U: Extractable, F: 'static + Fn(&mut T) -> &mut U
    {
        unsafe { f(&mut *self.ptr) }
    }
}

impl<T> Drop for HalfBox<T> {
    // Really, half-boxes should be linear types,
    // to avoid space leaks. Since rust only has affine types,
    // we replace the compile-time check by a run-time check.
    // FIXME: find a lint which looks to see if this is ever used
    fn drop(&mut self) {
        panic!("Half objects should not be reclaimed")
    }
}

impl<T> std::ops::Deref for HalfBox<T> {
    type Target = T;
    fn deref(&self) -> &T {
        unsafe { &*self.ptr }
    }
}

// We can implement doubly linked lists using half-boxes.

struct Queue<T> {
    length: u64,
    ends: Option<(HalfBox<Cell<T>>,HalfBox<Cell<T>>)>,
}

struct Cell<T> {
    item: T,
    left: Option<HalfBox<Cell<T>>>,
    right: Option<HalfBox<Cell<T>>>,
}

impl<T> Drop for Queue<T> {
    fn drop(&mut self) {
        // Make sure we don't panic dropping half-boxes.
        while self.length > 0 { self.pop(); }
    }
}

impl<T> Queue<T> {
    fn new() -> Queue<T> {
        Queue {
            length: 0,
            ends: None
        }
    }
    fn push<'a>(&'a mut self, value: T) where T:'a {
        self.length = self.length + 1;
        let (mut cell1, cell2) = HalfBox::new(Cell::new(value));
        if let Some((mut first, last)) = self.ends.take() {
            *first.extract(Cell::mut_left) = Some(cell2);
            *cell1.extract(Cell::mut_right) = Some(first);
            self.ends = Some((cell1, last));
        } else {
            self.ends = Some((cell1, cell2));
        }
    }
    fn pop<'a>(&'a mut self) -> Option<T> {
        if let Some((first, mut last1)) = self.ends.take() {
            self.length = self.length - 1;
            let last2 = if let Some(mut second_last) = last1.extract(Cell::mut_left).take() {
                let last2 = second_last.extract(Cell::mut_right).take().unwrap();
                self.ends = Some((first, second_last));
                last2
            } else {
                first
            };            
            let last = last1.whole(last2);
            Some(last.item)
        } else {
            None
        }
    }
}

impl<T> Cell<T> {
    fn new(item: T) -> Cell<T> {
         Cell {
             item: item,
             left: None,
             right: None,
         }
    }
    fn mut_left(&mut self) -> &mut Option<HalfBox<Cell<T>>> {
        &mut self.left
    }
    fn mut_right(&mut self) -> &mut Option<HalfBox<Cell<T>>> {
        &mut self.right
    }
}

// A quick check
// Note that we are pushing mutable refs onto the queue,
// so this is testing that the queue works for mutable data,
// not just copyable data.
fn main() {
    println!("Hello");
    let mut x=0;
    let mut y=2;
    let mut z=3;
    let mut queue = Queue::new();
    queue.push(&mut x);
    queue.push(&mut y);
    queue.push(&mut z);
    let xx = queue.pop().unwrap();
    let yy = queue.pop().unwrap();
    let zz = queue.pop().unwrap();
    *xx = *xx + 1;
    println!("Hello, queue item {:?}.", *xx);
    println!("Hello, queue item {:?}.", *yy);
    println!("Hello, queue item {:?}.", *zz);
    println!("Goodbye");
}