Soundness of "existential lifetime" erasure

_question.md

[These posts have been extracted from this Discord conversation, so as not to require readers to use their Discord account to read it 😔]

Question

HI!

Question and idea about narrowing lifetime of mutable references.

In rust code when developing finite state machines, behaviour trees and other algorithms we often need to pass around Context on which these algorithms will work.

If Context only contains shared references to data, then everything can be coerced to one lifetime

struct Context<'a> {
    ref1: &'a SomeData1<'a>,
    ref2: &'a SomeData2<'a, 'a, 'a>,
}

But if we need mutable references and SomeData contains mutable references itself, then a lot of lifetimes are introduced:

struct Context<'a, 'w, 's> {
    ref1: &'a mut SomeData1<'w>,
    ref2: &'a mut SomeData2<'w, 's>,
}

And we can not shorten mutable reference lifetimes as it could be unsound.

Rust does not allow narrowing the mutable references

Real life example from bevy:

struct Context<'a, 'w, 's>{
    query_1: &'a mut Query<'w, 's, ...>,
    item: &'a mut QueryItem<'w>,
}

And it gets even worse if i need to pass &'c mut &'b mut Context<'a, 'w, 's> (mutable reference of mutable reference if one algorithm uses another algorithm inside it and so on)

It would be nice if all lifetimes could be constrained to one shortest lifetime, but it is not sound due to this:

fn overwrite<T: Copy>(input: &mut T, new: &mut T) {
    *input = *new;
}

fn main() {
    let mut forever_str: &'static str = "hello";
    {
        let string = String::from("world");
        overwrite(&mut forever_str, &mut &*string);
    }
    // Oops, printing free'd memory
    println!("{}", forever_str);
}

So i had an idea: Add new lifetime modifier to rust to mark that only 'static lifetime data can be assigned to data accessed through lifetime with this new modifier. Then this problem would be resolved.

For example, lets mark this new lifetime in code as ~a.

Then code like this would be possible:

// Simplifying mutable references
fn new_lifetime<'a, 'b: 'a, T>(val: &'a mut &'b mut T) -> &~a mut T {
     val
}

// Context example to modify static data
struct Foo<'a> {
    buff: &'a mut String
}

struct Context<~f> {  // We do not need to track two lifetimes
    foo: &~f mut Foo<~f>
}

fn test<'f, 'a>(foo: &'f mut Foo<'a>) {
    let ctx = Context { foo };
    *ctx.foo.buff = String::new("New value!"); // Static data can be modified
}

// Bevy example where we need to track only shortest lifetime
struct Context<~a>{
    query_1: &~a mut Query<~a, ~a, ...>,
    item: &~a mut QueryItem<~a>,
}

Longer idea explanation: https://www.reddit.com/r/rust/comments/13wkx2b/idea_of_a_new_lifetime_modifier_to_avoid_lifetime/

Wanted to get expert opinion on this idea because something like this could simplify a lot of code in my case.

Would something like this be possible in rust type system in future, feasible? How do you handle such Context structures?

answer_1.md

[I start answering here]

Soundness of existential lifetime

FWIW, regarding soundness, this is exactly the + 'lt of dyns . Taking the real-life example of:

struct Context<'a, 'w, 's>{
    query_1: &'a mut Query<'w, 's, ...>,
    item: &'a mut QueryItem<'w>,
}

if you restrict the API of a given Context instance to operations that do not name/care-about 'w, 's, …, then you can define that API as a trait IsContext { … }, and then replace Context<'a, 'w, 's> with dyn 'a + IsContext.

So, provided proper API reduction, then replacing a bunch of lifetimes with their intersection is sound.

Higher-Kinded-Types API to the rescue:

Now to do this without involving dynamic dispatch, thanks to HKTs:

trait L2Gat {
    type Of<'w, 's>;
}
// we have:
type ContextGat<'a> = For!(<'w, 's> Context<'a, 'w, 's>);
                 // ~ dyn for<'w, 's> L2Gat<Of<'w, 's> = Context<'a, 'w, 's>>

pub
struct OneLifetime<'a, C : L2Gat>(
    C::Of<'a, 'a>,
);

impl<'a, C : L2Gat> OneLifetime<'a, C> {
    pub
    fn new<'w : 'a, 's : 'a>(it: C::Of<'w, 's>)
      -> Self
    {
         Self(unsafe { ::core::mem::transmute(it) })
    }

    pub
    fn with_inner<R>(self, scope: impl for<'w, 's> FnOnce(C::Of<'w, 's>) -> R)
      -> R
    {
        let yield_ = scope;
        yield_(self.0)
    }

    // ditto for `&self` and `&mut self`.
}

answer_1_demo.md

#![feature(unboxed_closures)]
mod hkts {
    pub
    trait For {
        type Of<'b>;
    }
    
    impl<F> For for F
    where
        F: for<'b> FnOnce<(&'b (), )>,
    {
        type Of<'b> = <F as FnOnce<(&'b (), )>>::Output;
    }
    
    #[macro_export]
    macro_rules! For {
        ( <$lt:lifetime> $T:ty $(,)? ) => (
            for<$lt> fn(&$lt ()) -> $T
        );
        ( $T:ty $(,)? ) => (
            fn(&'_ ()) -> $T
        );
    }
}
use hkts::For;

pub
struct OneLifetime<'a, C : For>(
    C::Of<'a>,
);

impl<'a, C : For> OneLifetime<'a, C> {
    pub
    fn new<'b : 'a>(it: C::Of<'b>)
      -> Self
    {
        Self(unsafe { ::core::mem::transmute(it) })
    }

    pub
    fn with_inner<R>(self, scope: impl for<'b> FnOnce(C::Of<'b>) -> R)
      -> R
    {
        let yield_ = scope;
        yield_(self.0)
    }

    pub
    fn with_ref<'r, R>(&'r self, scope: impl for<'b> FnOnce(&'r C::Of<'b>) -> R)
      -> R
    {
        let yield_ = scope;
        yield_(&self.0)
    }

    pub
    fn with_mut<'r, R>(&'r mut self, scope: impl for<'b> FnOnce(&'r mut C::Of<'b>) -> R)
      -> R
    {
        let yield_ = scope;
        yield_(&mut self.0)
    }
}

type Example<'a> = For!(<'b> &'a mut &'b mut String);

pub
fn creation<'a, 'b>(r: &'a mut &'b mut String)
  -> OneLifetime<'a, Example<'a>>
//   -> impl 'a + Sized
{
    OneLifetime::<For!(&'a mut &'_ mut String)>::new(r)
}

pub
fn usage<'a>(
    r: OneLifetime<'a, Example<'a>>,
    evil: &'a mut String,
)
{
    r.with_inner(move |r: &'a mut &'_ mut String| {
        **r = "..".into(); // OK
        *r = Box::leak(Box::new(String::from("…"))); // OK
        *r = evil; // Error!
    })
}

fn main() {}

yields:

   Compiling playground v0.0.1 (/playground)
error: lifetime may not live long enough
  --> src/main.rs:84:9
   |
76 | fn usage<'a>(
   |          -- lifetime `'a` defined here
...
84 |         *r = evil; // Error!
   |         ^^^^^^^^^ assignment requires that `'a` must outlive `'static`

error: could not compile `playground` (bin "playground") due to previous error

• Playground

answer_2.md

Replacing unsafe with dyn and Boxing

I guess we can circle back to my original dyn comment by realizing that the with_ functions represent such an API

#![forbid(unsafe_code)] // by the magic of `dyn`, no need for `unsafe`!

type _Problem<'a, 'b> = &'a mut &'b mut String;
// Objective: an `impl 'a` (no `'b` mentioned whatsoever!) which can be used as such

// `'b`-less API
trait Trait<'a> {
    // Box, `dyn FnOnce`, and lack of `-> R` to be `dyn`-safe
    fn with_inner(
        self: Box<Self>,
        scope: Box<dyn FnOnce(&'a mut &'_ mut String)>,
    );
}

fn _demo<'a, 'b>(r: &'a mut &'b mut String)
  -> Box<dyn 'a + Trait<'a>> // <- no `'b`!
{
    impl<'a, 'b> Trait<'a> for &'a mut &'b mut String {
        fn with_inner(
            self: Box<Self>,
            scope: Box<dyn FnOnce(&'a mut &'_ mut String)>,
        )
        {
            let yield_ = scope;
            yield_(*self)
        }
    }

    Box::new(r)
}

• Demo