intlist.rs

#![feature(if_let)]

use nomove::{freeze, freeze_box, FreezeSlice, NoMoveGuard};
use std::cell::Cell;

mod nomove {
    pub struct NoMoveGuard<T> {
        pub data: T,
        no_copy: ::std::kinds::marker::NoCopy,
    }

    pub trait FreezeSlice<'a, 'b, T> {
        fn freeze(self) -> &'a mut [&'b mut NoMoveGuard<T>];
    }

    impl<'a, 'b, T> FreezeSlice<'a, 'b, T> for &'a mut [&'b mut T] {
        #[inline]
        fn freeze(self) -> &'a mut [&'b mut NoMoveGuard<T>] {
            for mut el in self.iter_mut() {
                freeze(*el);
            }
            unsafe { ::std::mem::transmute(self) }
        }
    }

    pub fn freeze<'a, T>(data: &'a mut T) -> &'a mut NoMoveGuard<T> {
        unsafe {
            // Give ourselves some scratch space to work with
            let mut tmp: NoMoveGuard<T> = NoMoveGuard {
                data: ::std::mem::uninitialized(),
                no_copy: ::std::kinds::marker::NoCopy
            };
            // Copy data to... itself, to prevent UB.  Sigh.  This should *really* not be
            // necessary.
            let t: *mut T = &mut tmp.data;
            ::std::ptr::copy_nonoverlapping_memory(t, &*data, 1);
            ::std::ptr::copy_nonoverlapping_memory(::std::mem::transmute(&mut *data), &tmp, 1);
            ::std::mem::transmute(data)
        }
    }

    pub fn freeze_box<'a, T>(mut data: Box<T>) -> Box<NoMoveGuard<T>> {
        freeze(&mut *data);
        unsafe { ::std::mem::transmute(data) }
    }
}

struct Node<'a, 'b, T: 'a + 'b, U: 'a + 'b> {
    data: T,
    prev: Cell<Option<&'a NoMoveGuard<Node<'a, 'a, T, U>>>>,
    next: Cell<Option<&'b NoMoveGuard<Node<'b, 'b, T, U>>>>,
}

impl<'a, T> Node<'a, 'a, T, T> {
    pub fn new(data: T) -> Node<'a, 'a, T, T> {
        Node { data: data, prev: Cell::new(None), next: Cell::new(None) }
    }
}

trait NodeLink<'a, 'b: 'd + 'e, 'd: 'a, 'e, T, U> {
    fn set_next<'c>(&'c self, next: Option<&'b NoMoveGuard<Node<'c, 'e, T, U>>>);
    fn set_prev<'c>(&'c self, prev: Option<&'a NoMoveGuard<Node<'c, 'e, T, U>>>);

    #[inline]
    fn iter(&'a self) -> Items<'a, Self> {
        Items { head: Some(self) }
    }
}

impl<'a: 'd + 'e, 'b: 'd + 'e, 'd: 'a, 'e: 'b, T, U> NodeLink<'a, 'b, 'd, 'e, T, U> for NoMoveGuard<Node<'a, 'b, T, U>> {
    fn set_next<'c>(&'c self, next: Option<&'b NoMoveGuard<Node<'c, 'e, T, U>>>) {
        if let Some(next) = self.data.next.get() {
            next.data.prev.set(None)
        }
        if let Some(next) = next {
            next.data.prev.set(Some(self));
        }
        self.data.next.set(next)
    }

    fn set_prev<'c>(&'c self, prev: Option<&'a NoMoveGuard<Node<'c, 'e, T, U>>>) {
        if let Some(prev) = self.data.prev.get() {
            prev.data.next.set(None)
        }
        if let Some(prev) = prev {
            prev.data.next.set(Some(self));
        }
        self.data.prev.set(prev)
    }
}

pub struct Items<'a, T:'a> {
    head: Option<&'a T>,
}

impl<'a, 'b, A> Iterator<&'a A> for Items<'a, NoMoveGuard<Node<'a, 'a, A, A>>> {
    #[inline]
    fn next(&mut self) -> Option<&'a A> {
        self.head.map(|head| {
            self.head = head.data.next.get();
            &head.data.data
        })
    }
}

fn baz<'a, T>(_x: &'a NoMoveGuard<Node<'a, 'a, T, T>>, _y: &'a NoMoveGuard<Node<'a, 'a, T, T>>, b: T) -> Box<NoMoveGuard<Node<'a, 'a, T, T>>> {
    let y_ = box Node::new(b);
    //let y = freeze(&mut y_);
    let y: Box<NoMoveGuard<Node<'a, 'a, T, T>>> + 'a = freeze_box(y_);
    //x.set_next(Some(&*y));
    y
}

fn main(){
    let mut x_ = Node::new((10u, 10u));
    let x = freeze(&mut x_);

    let mut y_ = Node::new((11, 11));
    let y = freeze(&mut y_);
    let y = &*y;

    x.set_next(Some(y));

    let mut foo = range(0, 10).map( |i| Node::new((i,i)) ).collect::<Vec<_>>();
    let mut bar_ = foo.iter_mut().collect::<Vec<_>>();
    let bar = bar_.as_mut_slice().freeze();

    for win in bar.windows(2) {
        win[0].set_next(Some(&*win[1]));
    }
    let mut z_ = Node::new((12,12));
    let z = freeze(&mut z_);
    y.set_next(Some(&*z));

    z.set_next(Some(&*bar[0]));
    println!("{}", x.iter().collect::<Vec<_>>());

    let mut w_ = Node::new((13, 13));
    let w = freeze(&mut w_);
    let w = baz(x, w, (14, 14));

    z.set_prev(None);
    //z.set_next(Some(&*x));
    println!("{}", x.iter().collect::<Vec<_>>());
    println!("{}", z.iter().collect::<Vec<_>>());
    z.set_prev(Some(&*w));
    println!("{}", w.iter().collect::<Vec<_>>());
}

intlist2.rs

#![feature(if_let)]

use std::cell::Cell;

struct Node<'a, 'b, T: 'a + 'b, U: 'a + 'b> {
    data: T,
    prev: Cell<Option<&'a Node<'a, 'a, T, U>>>,
    next: Cell<Option<&'b Node<'b, 'b, T, U>>>,
    // Not NoSync (would require atomic ptrs probably) but safe in a single threaded context, because
    // all the nodes are nonmovable.  We can use Cell because & is Copy.
    
}

impl<'a, T> Node<'a, 'a, T, T> {
    #[inline]
    pub fn new(data: T) -> Node<'a, 'a, T, T> {
        Node { data: data, prev: Cell::new(None), next: Cell::new(None) }
    }
}

trait NodeLink<'a, 'b: 'd + 'e, 'd: 'a, 'e, T, U> {
    fn set_next<'c>(&'c self, next: Option<&'b Node<'c, 'e, T, U>>);
    fn set_prev<'c>(&'c self, prev: Option<&'a Node<'c, 'e, T, U>>);

    #[inline]
    fn iter(&'a self) -> Items<'a, Self> {
        Items { head: Some(self) }
    }
}

impl<'a: 'd + 'e, 'b: 'd + 'e, 'd: 'a, 'e: 'b, T, U> NodeLink<'a, 'b, 'd, 'e, T, U> for Node<'a, 'b, T, U> {
    #[inline]
    fn set_next<'c>(&'c self, next: Option<&'b Node<'c, 'e, T, U>>) {
        if let Some(next) = self.next.get() {
            next.prev.set(None)
        }
        if let Some(next) = next {
            next.prev.set(Some(self));
        }
        self.next.set(next)
    }

    #[inline]
    fn set_prev<'c>(&'c self, prev: Option<&'a Node<'c, 'e, T, U>>) {
        if let Some(prev) = self.prev.get() {
            prev.next.set(None)
        }
        if let Some(prev) = prev {
            prev.next.set(Some(self));
        }
        self.prev.set(prev)
    }
}

pub struct Items<'a, T:'a> {
    head: Option<&'a T>,
}

impl<'a, 'b, A> Iterator<&'a A> for Items<'a, Node<'a, 'a, A, A>> {
    #[inline]
    fn next(&mut self) -> Option<&'a A> {
        self.head.map(|head| {
            self.head = head.next.get();
            &head.data
        })
    }
}

fn baz<'a, T>(_x: &'a Node<'a, 'a, T, T>, _y: &'a Node<'a, 'a, T, T>, b: T) -> Box<Node<'a, 'a, T, T>> {
    let y_ = box Node::new(b);
    let y = y_;
    //x.set_next(Some(&*y));
    y
}

fn biz<'a, T>(x: &'a Node<'a, 'a, T, T>, y: &'a Node<'a, 'a, T, T>) {
    x.set_next(Some(y));
}

fn main(){
    let mut f = 10i;
    let mut x_ = Node::new((10u, 10u, &mut f));
    let x = &mut x_;

    let mut f = 11;
    let mut y_ = Node::new((11, 11, &mut f));
    let y = &mut y_;
    let y = &*y;

    x.set_next(Some(y));

    const COUNT: uint = 10;
    let mut fa = [0, .. COUNT];
    let mut foo = range(0, COUNT).zip(fa.iter_mut()).map( |(i, f)| Node::new((i,i, f)) ).collect::<Vec<_>>();
    let mut bar_ = foo.iter_mut().collect::<Vec<_>>();
    let bar = bar_.as_mut_slice();

    for win in bar.windows(2) {
        win[0].set_next(Some(&*win[1]));
    }
    let mut f = 12;
    let mut z_ = Node::new((12,12, &mut f));
    let z = &mut z_;
    y.set_next(Some(&*z));

    z.set_next(Some(&*bar[0]));
    println!("{}", x.iter().collect::<Vec<_>>());
    let mut f = 13;
    let mut w_ = Node::new((13, 13, &mut f));
    let w = &mut w_;
    let mut f = 14;
    let w = baz(x, w, (14, 14, &mut f));

    z.set_prev(None);
    //z.set_next(Some(&*x));
    println!("{}", x.iter().collect::<Vec<_>>());
    println!("{}", z.iter().collect::<Vec<_>>());
    z.set_prev(Some(&*w));
    println!("{}", w.iter().collect::<Vec<_>>());
    biz(x, z);
    println!("{}", x.iter().collect::<Vec<_>>());
}

nomove.rs

use nomove::{NoMove, NoMoveGuard};

mod nomove {
    pub struct NoMoveGuard<T> {
        pub data: T,
        no_copy: ::std::kinds::marker::NoCopy,
    }

    pub trait NoMove {
        fn freeze<'a>(&'a mut self) -> &'a mut NoMoveGuard<Self> {
            unsafe { ::std::mem::transmute(self) }
        }
    }

    impl<T> NoMove for T {}
}

fn move_thing<T>(first: &NoMoveGuard<T>, second: &NoMoveGuard<T>) {
    let _z = first;
    let _z = second;
}

fn main(){
    let mut x_ = ();
    let x = x_.freeze();
    
    // error: cannot move out of `x_` because it is borrowed
    //let z = x_;

    let mut y_ = ();
    let y = y_.freeze();

    // error: cannot move out of `y_` because it is borrowed
    // let z = y_; 
    move_thing(x, y);

    assert_eq!(std::mem::size_of::<NoMoveGuard<()>>(), 0)
}