Safe interface for a singly linked list of mutable references

@quinedot it isn’t sound.

mod m {
    pub trait Cursor<T> {
        fn next(&mut self) -> Option<&mut dyn Cursor<T>>;
        fn into_next(&mut self) -> Option<&mut Self>
        where
            Self: Sized;
        fn data(&self) -> &T;
        fn data_mut(&mut self) -> &mut T;
    }

    impl<'a, T> Cursor<T> for List<'a, T> {
        fn next(&mut self) -> Option<&mut dyn Cursor<T>> {
            match &mut self.next {
                Some(nxt) => Some(&mut **nxt),
                None => None,
            }
        }
        fn into_next(&mut self) -> Option<&mut Self>
        where
            Self: Sized,
        {
            self.next().map(|r| {
                let ptr = r as *mut dyn Cursor<T> as *mut Self;
                // Actually unsound, see main below
                unsafe { &mut *ptr }
            })
        }
        fn data(&self) -> &T {
            &self.data
        }
        fn data_mut(&mut self) -> &mut T {
            &mut self.data
        }
    }

    pub struct List<'a, T> {
        next: Option<&'a mut dyn Cursor<T>>,
        pub data: T,
    }

    impl<'a, T> List<'a, T> {
        pub fn append(&mut self, data: T) -> List<'_, T> {
            List {
                next: Some(self),
                data,
            }
        }

        pub fn cursor(&mut self) -> &mut dyn Cursor<T> {
            self
        }

        pub fn singleton(data: T) -> Self {
            Self { next: None, data }
        }
    }
}

use m::*;


fn main() {
    let mut zero = List::singleton(String::new());
    
    let mut one = List::singleton(String::from("Hello World!"));

    *zero.append(String::new()).into_next().unwrap() = one.append(String::new());

    let s: &str = zero.next().unwrap().data();

    println!("borrowed: {}", s);

    let string: String = std::mem::take(one.data_mut());

    println!("owner: {}", string);
    drop(string);

    println!("use after free: {}", s);
}

(rust explorer / playground doesn’t work at the moment)

borrowed: Hello World!
owner: Hello World!
use after free: ��Y�Ku�
3 Likes