Safe interface for a singly linked list of mutable references

So I just saw Lifetime of mutable reference and it gave me a bit of inspiration.

TLDR of the context: OP wanted to write a singly linked list where each node had a mutable reference to the next one. That is, something like this:

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

Experienced rustaceans will have noticed it immediately: &'a mut List<'a, T> is a famous antipattern that requires any such reference to be borrowed forever until they go out of scope. The reason comes down to the fact that &mut U is invariant in U, so we cannot shorten the lifetimes it references while we have a mutable reference to it. In turn the reason &mut U is invariant is because you can both read and write to the U, and if we allowed to shorten its lifetime while pointed by the mutable reference we could write a U with shorter lifetimes while the original owner of it still expects it to be valid for the bigger lifetime. In our case this translates to overwriting any of the next links, but this got me thinking: this is often not what this is used for. Instead you most often just create a new link referencing the old one, and "pop" it by just letting the last node go out of scope. next is almost never overwritten, only T is mutated. Unfortunately there's no way to express this in safe Rust, but what if we used unsafe and wrote an interface that guaranteed this?

So here's my attempt:

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

impl<'a, T> List<'a, T> {
    /// SAFETY: The caller must not allow writing or replacing
    /// any of the `next` fields of the list.
    unsafe fn launder_lifetime(&mut self) -> &mut List<'_, T> {
        // SAFETY: Since next is never written to, we can consider
        // List<'a, T> as if it was covariant in 'a, thus allowing this coercion.
        unsafe { &mut *(self as *mut List<'a, T>).cast() }
    }

    pub fn cursor(&mut self) -> ListRef<'_, T> {
        // SAFETY: ListRef doesn't allow writing/replacing any of the `next` fields.
        ListRef(unsafe { self.launder_lifetime() })
    }
    
    pub fn append(&mut self, data: T) -> List<'_, T> {
        // SAFETY: List doesn't allow writing/replacing any of the `next` fields.
        List {
            next: Some(unsafe { self.launder_lifetime() }),
            data,
        }
    }
}

/// This is essentially a `&'a mut List<'a, T>`
/// that doesn't allow directly writing to it.
pub struct ListRef<'a, T>(&'a mut List<'a, T>);

impl<'a, T> ListRef<'a, T> {
    pub fn next(&mut self) -> Option<ListRef<'_, T>> {
        self.0.next.as_deref_mut().map(|list| list.cursor())
    }
    
    pub fn into_next(self) -> Option<ListRef<'a, T>> {
        self.0.next.as_deref_mut().map(|list| list.cursor())
    }
    
    pub fn data(&self) -> &T {
        &self.0.data
    }
    
    pub fn data_mut(&mut self) -> &mut T {
        &mut self.0.data
    }
}

This is essentially the List mentioned above, except next is private and there's no way to mutate it. ListRef is also needed to allow iterating the previous nodes while retaining mutable access to the data. Using &mut List<'???, T> for it is not possible because there's no lifetime to put there since the correct one has been forgotten.

Sidenote: in some sense this feels like Pin, with List being !Unpin and next being structurally pinned (while data is not). However all the pinning apart from preventing uncontrolled mutations are not really useful here, and Pin being just a way to express unsafe contracts means it doesn't give us the tools to actually implement it (at best it would allow replacing ListRef<'a, T> with Pin<&'a mut List<'a, T>>).

What do you think? Is my code safe? Or have I missed something?

This reminds me of the covariance of all dyn Trait + 'erased, where the soundness arguments rests upon the limited types of access trait objects allow.

Here's something similar using a dyn Trait. It can be unsafe-free without into_next, which I don't think is that useful anyway.[1]

Edit: Worse than useless, it's unsound.


  1. ? for the example at least ↩︎

3 Likes

As you've mentioned, the problem is variance. And the solution is easy - make them actually variant. Replace &'a mut Node<'a> with &'a Node<'a> or &'a RefCell<Node<'a>>(or similar). Now everything is safe and usually the cost is insignificant.

&RefCell<T> is invariant in T and thus has the same "borrowed forever" problems as &mut T.

2 Likes

All you need for into_next is to put the reference itself into a trait object. Which, well, it means boxing, but so what, this isn’t about efficiency:

pub struct List<'a, T> {
    next: Option<ListRef<'a, T>>,
    pub data: T,
}

impl<'a, T> List<'a, T> {
    pub fn cursor(&mut self) -> ListRef<'_, T> {
        ListRef(Box::new(self))
    }

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

trait ListRefInner<T> {
    fn reborrow(&mut self) -> ListRef<'_, T>;

    fn next(&mut self) -> Option<ListRef<'_, T>>;

    fn into_next<'a>(self: Box<Self>) -> Option<ListRef<'a, T>>
    where
        Self: 'a;

    fn data(&self) -> &T;

    fn data_mut(&mut self) -> &mut T;
}
impl<'b, 'c, T> ListRefInner<T> for &'b mut List<'c, T> {
    fn reborrow(&mut self) -> ListRef<'_, T> {
        self.cursor()
    }

    fn next(&mut self) -> Option<ListRef<'_, T>> {
        self.next.as_mut().map(ListRef::reborrow)
    }

    fn into_next<'a>(self: Box<Self>) -> Option<ListRef<'a, T>>
    where
        Self: 'a,
    {
        self.next.as_mut().map(ListRef::reborrow)
    }

    fn data(&self) -> &T {
        &self.data
    }

    fn data_mut(&mut self) -> &mut T {
        &mut self.data
    }
}

/// This is essentially a `&'a mut List<'a, T>`
/// that doesn't allow directly writing to it.
pub struct ListRef<'a, T: 'a>(Box<dyn ListRefInner<T> + 'a>);

impl<'a, T> ListRef<'a, T> {
    pub fn reborrow(&mut self) -> ListRef<'_, T> {
        self.0.reborrow()
    }

    pub fn next(&mut self) -> Option<ListRef<'_, T>> {
        self.0.next()
    }

    pub fn into_next(self) -> Option<ListRef<'a, T>> {
        self.0.into_next()
    }

    pub fn data(&self) -> &T {
        self.0.data()
    }

    pub fn data_mut(&mut self) -> &mut T {
        self.0.data_mut()
    }
}

(playground)

So, yes, by the alternative implementation above, your safe API should be sound.

3 Likes

I think it's fantastic. Both the boxed and unboxed versions would be useful.

Nevermind, this works just as well without boxes (and with surprisingly little code change). What did you do wrong? :thinking: (Edit: Oh I see, your into_next returns a &mut List<…> reference…, I'll have to think about the soundness of that some more.)

pub struct List<'a, T> {
    next: Option<ListRef<'a, T>>,
    pub data: T,
}

impl<'a, T> List<'a, T> {
    pub fn cursor(&mut self) -> ListRef<'_, T> {
        ListRef(self)
    }

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

trait ListRefInner<T> {
    fn reborrow(&mut self) -> ListRef<'_, T>;

    fn into_next(&mut self) -> Option<ListRef<'_, T>>;

    fn data(&self) -> &T;

    fn data_mut(&mut self) -> &mut T;
}
impl<'b, 'c, T> ListRefInner<T> for List<'c, T> {
    fn reborrow(&mut self) -> ListRef<'_, T> {
        self.cursor()
    }

    fn into_next(&mut self) -> Option<ListRef<'_, T>> {
        self.next.as_mut().map(ListRef::reborrow)
    }

    fn data(&self) -> &T {
        &self.data
    }

    fn data_mut(&mut self) -> &mut T {
        &mut self.data
    }
}

/// This is essentially a `&'a mut List<'a, T>`
/// that doesn't allow directly writing to it.
pub struct ListRef<'a, T: 'a>(&'a mut dyn ListRefInner<T>);

impl<'a, T> ListRef<'a, T> {
    pub fn reborrow(&mut self) -> ListRef<'_, T> {
        self.0.reborrow()
    }

    pub fn next(&mut self) -> Option<ListRef<'_, T>> {
        self.0.into_next()
    }

    pub fn into_next(self) -> Option<ListRef<'a, T>> {
        self.0.into_next()
    }

    pub fn data(&self) -> &T {
        self.0.data()
    }

    pub fn data_mut(&mut self) -> &mut T {
        self.0.data_mut()
    }
}

(playground)

1 Like

@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

It is the "law of unsafety". If you are not 110% sure it is sound, it isn't.

1 Like

Thank you everyone! I didn't think of trait objects, that's really interesting. It's a bit unfortunate that the fully safe implementation cannot be as efficient as the unsafe one, but at least it shows it's possible.