4
\$\begingroup\$

I recently had this (admittedly slightly crazy idea) on how to design a building block that can be used in safe Rust to build self-referential structs. Unlike gsrs or selfref it works completely without macros. I will present my idea next, my question is mainly if it is indeed impossible to create UB from safe code using these primitives. Also, suggestions how to increase the usability or potential conflicts with other patterns/techniques are welcom.

I will explain the following code in the text, should it be transformed into a library, this would of course be migrated into doc-comments.

The basic idea is to provide a "container" that should look like

pub struct SelfReferentialAtom<T, U> {
    referenced_part: Box<T>,
    referencing_part: U
}

impl<T, U> SelfReferentialAtom<T, U> {

    pub fn referenced_part<'a>(&'a self) -> &'a T {
        &self.referenced_part
    }

    pub fn referencing_part<'a>(&'a self) -> &'a U {
        &self.referencing_part
    }
}

where referencing_part may contain a reference on the internals of referenced_part. If no mutable access to referenced_part is granted, this should be safe (since the content of referenced_part is Boxed and thus won't be moved, even if the parent struct is).

The obvious difficulty here is: How do we create an instance of SelfReferentialAtom, and which lifetime should references in referencing_part have. Let's answer the second question first.

A new reference type: ILRef

As there is no 'self-lifetime (and despite it being commonly requested in various places, I cannot think how it could make sense), we cannot use standard references &'static _ or &'a _. Since we want to use safe Rust, raw pointers also are not an option. Hence we must define our own reference type:

#[derive(Debug)]
pub struct ILRef<'max_lifetime, T: ?Sized> {
    data: PhantomData<&'max_lifetime T>,
    pointer: NonNull<T>
}

impl<'max_lifetime, T: ?Sized> ILRef<'max_lifetime, T> {

    pub fn project<F, U: ?Sized>(&self, f: F) -> ILRef<'max_lifetime, U>
        where for<'b> F: FnOnce(&'b T) -> &'b U
    {
        ILRef { data: PhantomData, pointer: NonNull::from(f(self.deref())) }
    }
}

impl<'max_lifetime, T: ?Sized> Deref for ILRef<'max_lifetime, T> {

    type Target = T;

    fn deref<'a>(&'a self) -> &'a Self::Target {
        unsafe { self.pointer.as_ref() }
    }
}

Why the name ILRef? It stands for "inherited lifetime reference", and with that I mean that the lifetime of the pointed-to-value is the lifetime of the reference object itself. Since the referencing_part of SelfReferentialAtom will contain the ILRefs, and lives for the same lifetime as referenced_part, we can say that as long as an ILRef object exists, its pointed-to-value is also valid - that is, as long as the ILRef object is properly managed by SelfReferentialAtom (more on that later).

Creating SelfReferentialAtoms

Now that we have the correct reference type, we can answer the first question: How to create a SelfReferentialAtom object. To do so safely, we provide a global function that ensures all the requirements are satisfied.

pub trait RefType {
    type Associated<'a>;
}

pub fn make_self_referential<T, F, UConstruct>(target: T, reference_creator: F) -> SelfReferentialAtom<T, UConstruct::Associated<'static>>
    where T: 'static,
        UConstruct: RefType,
        UConstruct::Associated<'static>: /* A note on this later */ Unmodifiable,
        F: for<'a> FnOnce(ILRef<'a, T>) -> UConstruct::Associated<'a>
{
    fn assert_same_memory<'a, T: ?Sized, UConstruct: RefType>(_liftetime_marker: &'a T) {
        assert!(std::mem::size_of::<UConstruct::Associated<'a>>() == std::mem::size_of::<UConstruct::Associated<'static>>());
        assert!(std::mem::align_of::<UConstruct::Associated<'a>>() == std::mem::align_of::<UConstruct::Associated<'static>>());
    }

    let target_box = Box::new(target);
    assert_same_memory::<_, UConstruct>(&target_box);
    let reference = reference_creator(ILRef { data: PhantomData, pointer: NonNull::from(&*target_box) });
    return SelfReferentialAtom {
        target: target_box,
        reference_holder: reference
    }
}

Due to how the Rust typesystem currently works, we unfortunately need the helper trait RefType which just specifies a type of reference with currently not yet determined lifetime. For example, this could be the standard reference &_ via

pub struct StdRefConstruct<T: 'static + ?Sized> {
    data: PhantomData<T>
}
impl<T: 'static + ?Sized> RefType for StdRefConstruct<T> {
    type Associated<'a> = &'a T;
}

or - the most important possibility - our new ILRef via

pub struct ILRefConstruct<T: 'static + ?Sized> {
    data: PhantomData<T>
}
impl<T: 'static + ?Sized> RefType for ILRefConstruct<T> {
    type Associated<'a> = ILRef<'a, T>;
}

The main point of make_self_referential() is now simple: We create the referenced object inside a Box, and create the referencing object using the given constructor function. We then trust that the interface of SelfReferentialAtom ensures that the referencing object does not live longer than the rerenced object, and so it is fine to give it access to a UConstruct::Associated<'static>, which would e.g. specialize to ILRef<'static, T>. Note that the pointed-to value does not necessarily have static lifetime (we also will never actually produce a &'static PointedToValue), this is just a "proxy" lifetime to give ILRef.

Why I believe this is safe

The important part is that ILRef can only be dereferenced when we have a reference to ILRef. If we can ensure that ILRef does not "leave" the SelfReferentialAtom, then references to it will only exist as long as the referenced value does. I can only think of two ways how ILRef could leave the SelfReferentialAtom:

  • It could be copied from the return value of referencing_part() - this is easy to prevent by making ILRef neither Clone nor Copy.
  • It could be moved out of the referencing object. Since we only give immutable access to that object, this would require interior mutability. To prevent this, we introduce the trait Unmodifiable - which basically just forbids interior mutability.
#![feature(auto_traits)]
#![feature(negative_impls)]

pub unsafe auto trait Unmodifiable {}

impl<T: ?Sized> !Unmodifiable for UnsafeCell<T> {}

Finally, we should also make sure that the reference to the referenced object cannot be extracted during the constructor function, but this is easy to ensure by declaring the type bounds as above as F: for<'a> FnOnce(&'a T) -> UConstruct::Associated<'a>, since now the only reference that could be safely extracted by an implementation of F has lifetime as long as an invocation of F.

The whole example

Try it out on the playground!

Making it more useful...

In practice, it would probably nicer to loosen some of the restrictions. I have the following ideas:

  • Allow copying the ILRef during the constructor function F, but not afterwards - e.g. by providing a Creator-Function instead of the reference itself. This allows the referencing object to have an arbitrary number of references to the referenced object.
  • Implementing a function to changed the referencing object for SelfReferentialAtom, using similar semantics as for the creation.

Edit: Rename InhRef to ILRef, according to J_H's comment.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Good work! naming nit: maybe call it ILRef ? I notice that my mental pronunciation, “inherited ref”, is (A.) not what you intended, and (B.) wrong. Names matter, and I fear the current proposed name might lead to more app level bugs than with an alternative name. \$\endgroup\$
    – J_H
    Jan 26 at 23:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.