About the soundess of a non 'static Any trait

Hi,

I'm writing a custom Entity Component System for my game (I like to do things myself, I know there's loads of existing solutions) and I wanted to allow the insertion of non-'static entities. This is non-trivial because the whole ECS engine works using the standard TypeId which cannot be used for non-'static types. This is pretty much how I fell in the rabbit hole of the infamous non-'static Any trait.

I've been reading a lot, mainly a retracted RFC and its related GitHub issues. The conclusion seems pretty clear : it's not possible. At least at the moment.

Another topic also tackles this particular issue and it's basically the same. Encoding lifetime information in TypeId is impossible.

But I don't see how this is a problem, though. Hear me out: I'm probably wrong. I didn't think about it for a long time (I started this whole journey last week).

Here is my idea (this is a playground link).

What do you think ? Is this solution sound ? I'm not sure how the variance of types can affect the implementation of OutlivedBy<'a> (I'm not even sure it has an impact on it), but for covariant lifetime parameters at least, I think it is pretty robust.


Turns out I'm not allowed to put more than two links in the post so here some useful links that you can Copy/Past.

Entity Component System - https://en.wikipedia.org/wiki/Entity_component_system
The TypeId type - https://doc.rust-lang.org/std/any/struct.TypeId.html
The Any trait - https://doc.rust-lang.org/std/any/trait.Any.html
Retracted RFC on relaxing the 'static bound on the type_id intrinsic - https://github.com/rust-lang/rfcs/blob/master/text/1849-non-static-type-id.md
The other topic talking about encoding lifetime information - https://internals.rust-lang.org/t/would-non-static-typeid-be-at-all-possible/14258

Most likely, good mindset!

Let me take a look and find flaws in the API and ways to abuse the API.


/// # Safety
///
/// If `Self`'s type constructor has lifetime parameters, all those parameters
/// must be supertypes of `'a`, meaning for every parameter `'p`, there must be
/// `'a: 'p`.
///
/// This is basically the opposite of `T: 'a`.

okay, wouldn’t this definition outrule &'a &'b (): OutlivedBy<'a>, since 'a and 'b are parameters (think of type RefRef<'a, 'b, T> = &'a &'b T;, but 'a: 'b is not necessarily the case? (In fact, for the type &'a &'b (), you’ll always have 'b: 'a, so that 'a: 'b is only the case if 'a == 'b.)

Just saying, because this implementation

unsafe impl<'a, T: ?Sized> OutlivedBy<'a> for &'a T {}

seems to be in conflict with that definition. (Note that a generic type T’ can contain further lifetime parameters.)


So the main function here,

fn downcast_ref<T: OutlivedBy<'a>>(self: &dyn 'a + Any) -> Option<&T>

seems to be able to take a &S such that S: 'a, coerced to &dyn 'a + Any, and turn it into any type &T such that type-ids match and T: OutlivedBy<'a>.

This means, (taking the actual verbal definition of OutlivedBy into account, not its inaccurate implementation) it’s still possible, with this method, to turn e.g. a reference to a struct Foo<'p1, 'p2, 'p3> where 'p1: 'a, 'p2: 'a, and 'p3: 'a, into a reference to Foo<'q1, 'q2, 'q3> where 'a: 'q1, 'a: 'q2, and 'a: 'q3. These requirements do ensure 'p1: 'q1, 'p2: 'q2, and 'p3: 'q3, but still, this conversion is only sound if Foo is covariant in its lifetime arguments.


So let’s take a counter-example, e.g. &'a Cell<&'a str>, then you can use your API to convert that into &'b Cell<&'b str> where 'a: 'b:

use std::cell::Cell;
fn bad_conversion<'a: 'b, 'b>(r: &'a Cell<&'a str>) -> &'b Cell<&'b str> {
    let x = &r as &(dyn 'b + Any);
    *x.downcast_ref::<&'b Cell<&'b str>>().unwrap()
}

Which can be abused

fn main() {
    let x: String = "Hello World!".into();
    let cell: Cell<&str> = Cell::new("");
    let r = bad_conversion(&cell);
    r.set(&*x);
    drop(x);
    println!("{}", cell.get()); // use-after-free of x
}
6 Likes

Hey, @steffahn ! Thanks for taking the time to break my solution apart. This is definitely what I need to understand things.

Wouldn't adding an OutlivedBy<'a> bound the the generic T in &'a T's implementation of OutlivedBy<'a> rule out &'a &'b () ? I mean, OutlivedBy<'a> can be implemented for references that are both outlived by 'a and that have generic lifetimes outlived by 'a.

unsafe impl<'a, T: ?Sized + OutlivedBy<'a>> OutlivedBy<'a> for &'a T {}

But this comes with an obvious flaw: it completely breaks the whole API.

Requiering T: OutlivedBy<'a> means that if I want to have T = u32, I must have u32: OutlivedBy<'a>. This is only possible if 'a = 'static - which is obviously not what I wanna do here, because it rules out my original sound solution.

I've been trying to repair this thing for the past hour and I cannot seem to find something that both works AND rules out the Cell<&str> situation. I'm gonna reply with this message as a proof of my good will, and obviously continue to search for a sound API because I have way too much free time right now.

I just spent another 30 minutes trying to break the API with a covariant lifetime.

use parking_lot::Mutex;

static GLOBAL: Mutex<&'static str> = parking_lot::const_mutex("");

fn evil_downcast<'a: 'b,'b, 'c>(input: &'a fn(&'static str)) -> &'b fn(&'c str) {
    let d = &input as &(dyn Any + 'b);
    *d.downcast_ref::<&'b fn(&'c str)>().unwrap()
}

fn init_global(s: &'static str) {
    *GLOBAL.lock() = s;
}

fn main() {
    let evil_func = *evil_downcast(&init_global);

    let string = String::from("Hello, world!");
    evil_func(string.as_str());
    drop(string);

    println:("{}", GLOBAL.lock()); // use-after-free of `string`
}

One last question though: if there was only one implementation of the OutlivedBy<'a> trait for &'a T where T: 'static (and eventually &'a mut T where T: 'static), would it be sound ? Because that basically only rules the example I provided in my first post in.

In fact, would it be sound for any type constructor F<'covariant, 'invariant, 'contravariant> ?

unsafe impl<'a> OutlivedBy<'a> for F<'a, 'static, 'static> {}

Yeah, this could indeed be sound. And similarly, you could probably do an

unsafe impl<'a> OutlivedBy<'a> for F<T> where T: OutlivedBy<'a> {}

as long as F is covariant in T.

Which means that the &'a T implementation could also work soundly with a T: OutlivedBy<'a> bound (since &'a T is covariant in T; unlike &'a mut T). Unfortunately, that’s a tradeoff because now only types that implement OutlivedBy are supported – the problem with the missing/impossible generic OutlivedBy<'a> for T where T: 'static impl comes in :sweat_smile:

Probably also it’s better if you also allowed for different lifetimes, i.e. &'a T: OutlivedBy<'b>, as long as 'b: 'a is fulfilled (and similarly for &mut T) (instead of requiring 'a and 'b to be exactly the same), so e.g.

unsafe impl<'a, 'b: 'a> OutlivedBy<'a> for &'b T where T: OutlivedBy<'a>

or

unsafe impl<'a, 'b: 'a> OutlivedBy<'a> for &'b T where T: 'static

Non-'static Any has been attempted many times before. I don't realistically think that it is reasonably solvable.

The thing is, the issue is not a matter of "adding one more bound". You can keep patching solutions and assume them to be sound, but eventually, some new, creative, and unforeseen way to abuse it will eventually rise.

This is a kind of problem that is better worked around rather than "solved" by dangerous uses of unsafe code. People have written ECSes in Rust before – non-'static downcasting is certainly not a hard requirement there.

Comex answered my pertinent question over at IRLO, and he specifically enumerated the possible solutions. The verdict is: it's not exactly impossible, it's just highly impractical.

1 Like

To be clear. Now, the T: OutlivedBy<'a> trait would now require

  • all non-covariant lifetimes to be 'static
  • some covariant lifetimes to be shorter than 'a
  • the remaining covariant lifetime to be 'static, too

The choice which of the covariant lifetimes have to be 'static and which have to be shorter than 'a is made once for each type in its T: OutlivedBy<'a> implementation, and it can be chosen arbitrarily without violating soundness.

E.g. the choice between

unsafe impl<'a, 'b: 'a> OutlivedBy<'a> for &'b T where T: OutlivedBy<'a>

and

unsafe impl<'a, 'b: 'a> OutlivedBy<'a> for &'b T where T: 'static

is the choice between requiring every covariant lifetime inside of the type T in a &'b T to be static vs. requiring some of them to be shorter than 'a as determined by the T: OutlivedBy<'a> implementation.


Actually,such a generic implementation is impossible/unsound anyways; I mixed up OutlivedBy<'a> for T where T: 'static and OutlivedBy<'static> for T where T: 'static; considering the characterization above, only the latter would be okay (but still it’s not accepted due to overlap). And only the latter is what you’ve proposed in your original code, anyway.

I think I'm gonna stick with some precise implementations of the trait for types that I trust, and probably remove it entierly when I finally convince myself that I don't need it. In the meantime, I'm donna look for new, hopefully more robust, solutions.

Thanks for taking the time to review my code!

Yeah, I've kind of understood that while I was reseaching a way to do this :sweat_smile:. I don't pretend that I can find a solution to that problem. I'm just trying to understand why the solution I thought about doesn't work. I was kind of expecting it because surely someone has already tried it. I know I will continue to think about it until I don't have new ideas.

Or you can simply put a unsafe fence before the critical section and ask the caller to be reasonable. I don't think this is something I'm gonna do, though. It's way to easy to shoot myself in the foot.

Of course not! I probably don't even need this. I simply thought it would be cool and tried to find how to do it. That's all! However, I do have some cases in mind where it could be useful. But it could be easiely worked around with 'static types - maybe slightly less efficiently though.

1 Like

(I know I deleted a post, I just didn't finished writing it and I just realized too late I could just edit)

Guess what, I think I a bit too stubborn because I kept looking for a sound solution. Once again, I'm posting this here because I want people to break it.

Tell me if I'm wrong, but given two Sized types T and U, having T: UT can be safely transmuted into U. For example, u32: u32 so it's safe to transmute u32 into u32. This is pretty obvious, but let's do it with references. 'a: 'b &'a u32: &'b u32&'a u32 can be safely transmuted into &'b u32.

This also work for contravariant and invariant lifetimes. 'T: Ufn(U): fn(T)fn(U) can be safely transmuted into fn(T). Also, Cell<T>: Cell<T> because Cell<T> is invariant in T.

If this is correct, then it should be possible to write somthing like this.

// Safety:
//
// `Self` must be a subtype of `T`.
unsafe trait SubtypeOf<T: ?Sized> {}

This trait can be implemented for any T that doesn't have lifetime paramters.

unsafe impl SubtypeOf<u32> for u32 {}

And the reasoning I did above can be used here. Rust doesn't have a T: U syntax but this is basically
the same thing.

// Safety:
//
// `&'a T` is covariant in `'a` so we have to require `'a: 'b`.
// `&'a T` is covariant in `T` so we have to require `T: U`.
unsafe impl<'a, 'b, U, T> SubtypeOf<&'b U> for &'a T
where
    'a: 'b,
    U: ?Sized,
    T: ?Sized + SubtypeOf<U>,
{}

// Safety:
//
// `fn(T)` is contravariant in `T` so we have to require `U: T`.
unsafe impl<U, T> SubtypeOf<fn(U)> for fn(T)
where
    U: SubtypeOf<T>,
{}

// Safety:
//
// This implementation requires `T` to be the same.
unsafe impl<T: ?Sized> SubtypeOf<Cell<T>> for Cell<T> {}

This pretty basic and not really useful. But this does mean that we can write a safe version of transmute.

/// Safely transmutes a `T` into an `U`.
fn safe_transmute<T, U>(value: T) -> U
where
    T: SubtypeOf<U>
{
    let value = std::mem::ManuallyDrop::new(value);
    unsafe { (&*value as *const T as *const U).read() }
}

Our problem is that TypeId equality completely forgets about lifetimes. But if we could somehow remember the type subtyping relationship of T and U regarding their lifetime parameters, it would be possible to write a fallible version of safe_transmute.


Introducing: my new attempt.

/// # Safety
///
/// Let `F` be the type constructor of `Self`.
///
/// * `'cov` must be the lifetime of all covariant lifetime paramters of `F`.
/// * `'con` must be the lifetime of all contravariant lifetime parameters of `F`.
/// * `'inv` must be the lifetime of all invariant lifetime parameters of `F`.
pub unsafe trait Any<'cov, 'con, 'inv> {
    fn type_id(&self) -> u64 { type_id::<Self>() }
}

From this, we can create our new safe_transmute. Let's call it checked_transmute.

/// Safely transmutes a `T` into an `U`.
fn checked_transmute<'cov_t, 'con_t, 'cov_u, 'con_u, 'inv, T, U>(value: T) -> Result<U, T>
where
    T: Any<'cov_t, 'con_t, 'inv>,
    U: Any<'cov_u, 'con_u, 'inv>,
    'cov_t: 'cov_u,
    'con_u: 'con_t,
{
    if type_id::<T>() == type_id::<U>() {
        let value = std::mem::ManuallyDrop::new(value);
        
        // Safety:
        // 
        // We know that T and U are equal in their IDs, meaning they can only
        // differ in their lifetimes.
        //
        // The signature of the function ensures that `U: T` as long as they are the only
        // only thing that differs is the lifetimes.
        //
        // This should be safe?
        Ok(unsafe { std::ptr::read(&*value as *const T as *const U) })
    } else {
        Err(value)
    }
}

The idea is that TypeId equality only check for half the requirements of a safe transmutation. Keeping the other half in Any's trait constructor (is that a thing ? A trait constructor ? You got it.)

If this function really is safe (and it probably isn't), then writing downcast_ref and downcast_mut is trivial.

This new Any trait is basically a generalization of the old OutlivedBy<'a> which only took covariant lifetimes in account.

Deriving Any isn't very difficult, but it's not possible to write a blanket implementation for any T with Rust's current syntax. Here is some examples (removed the unsafe impl for clarity).

// Safety:
//
// `str` doesn have lifetime paramters. Any lifetime works for this type.
impl<'cov, 'con, 'inv> Any<'cov, 'con, 'inv> for str {}

// Safety:
//
// `&'a T` is covariant in `'a`, so we have to put `'cov` in its place.
// `&'a T` is covariant in `T`, so we simply have to forward the lifetimes.
impl<'cov, 'con, 'inv, T> Any<'cov, 'con, 'inv> for &'cov T
where
    T: Any<'cov, 'con, 'inv>,
{}

// Safety:
//
// `Cell<T>` is invariant in `T`, so all the lifetimes of `T` have to be frozen.
impl<'cov, 'con, 'inv, T> Any<'cov, 'con, 'inv> for Cell<T>
where
    T: Any<'inv, 'inv, 'inv>,
{}

// Safety:
//
// `fn(T)` is contravariant in `U`, so the lifetimes have to be forwarded to `T` by
// swapping the `'cov` and `'con` lifetimes.
impl<'cov, 'con, 'inv, T> Any<'cov, 'con, 'inv> for fn(T)
where
    T: Any<'con, 'cov, 'inv>,
{}

Try it on the playground!

1 Like

Maybe that's clear to you already, but let me note it nonetheless: Not every type will implement your Any trait. Yes, every type constructor will, but not every type; e.g. a type containing 2 different invariant lifetime arguments won't implement Any<'cov, 'con, 'inv> for any choice of 'cov/'con/'inv.

That being said, the trait itself and the checked_transmute function as well as the demonstration implementations seem sound to me (first impression, no thorough analysis done on my end). One could probably even write a safe macro for writing these unsafe impls which generates some code that's able to test the variance assumptions that the respective implementations make by creating a function that fails to compile when the variance information given to the macro is inaccurate.

2 Likes

I kinda had the intuation that this Any implementation would be too restrictive to work for every type but I hadn't really thought about it more than that. I was mainly excited to find something that somewhat worked.

It should be possible to create a version of Any that have 'inv0, 'inv1, ..., 'inv31 to cover realistically every possible case, though. I mean, if we have a derive macro, using a lot of lifetimes isn't really a problem. If the type requires multiple invariant lifetimes, they use one more slot, and the others can just be "free".

Thanks for looking at it, though.

So, I haven't read the whole thread in detail, sorry, but this reminds me of the following very interesting attempt:

We'll need to disregard something horrendous which that crate does: it assumes that the vtable of Any will have the same layout as the vtable of trait Trait for a Trait with a type_id method. Worst thing is, it isn't even a necessary hack for a lifetime-infected Any (it's just something the author did to improve the ergnomics between Any_1<'lt> and Any (see below), which is a pity since it means that that crate is unsound because of this silly thing when the actual subtle stuff is done correctly! :sweat_smile:)

Now, regarding the lifetime-infected Any design in that crate, I believe, contrary to what would be expected for something as subtle and error-prone as Any + lifetimes, that it is sound! The counter-part is that the trait is awfully restrictive, or, at the very least, very unergonomics, so it may not be that useful in practice.

A sound non-'static (partial) type erasure

The key idea of that crate is as follows:

  • We have non-lifetime infected types, which are 'static, and thus candidates for Any;

  • We have types infected with multiple lifetimes, or just generic over types, which, by construction, could lead to multiple lifetimes. These are not (directly) supported by the design.1

  • And we happen to have types which are infected with at most one lifetime parameter. This is the category of types that better_any tries to support.

So, given a type which is exactly generic over one lifetime parameter, such as struct Foo<'lt>, or &'lt (impl 'static), etc., we can actually split the type in three components:

  • the at-compile-time type-encoded lifetime;

  • the rest of the static / compile-time / type-encoded data: the type but without the lifetime;

  • the runtime data of an instance.

In the case of a 'static type, the first bullet does not exist, and we know we can thus handle the two remaining layers with the Any type, by converting the second bullet into part of the third one (the TypeId):

  • Can be handled by Any and its runtime TypeId:

    • non-lifetime-infected type information;

    • runtime data of the instance;

  • Cannot be handled by Any:

    • the lifetime information encoded in the type, which for this category of types, is exactly one lifetime.

The solution then is clear:

let's type erase everything but that lifetime!

This is thus achieved by having not one special "smarter" Any-like trait, but an infinite family of such: a lifetime-infected trait.

unsafe
trait Lifetime_1<'lt> {
    type WithoutTheLifetime : 'static;
}

trait Any_1<'lt> {
    fn type_id(&self) -> TypeId;
}
impl<'lt, T : Lifetime_1<'lt>> Any_1<'lt> for T {
    fn type_id(&self) -> TypeId {
        TypeId::of::<
            <Self as Lifetime_1<'lt>>::WithoutTheLifetime
        >()
    }
}
impl<'lt> dyn Any_1<'lt> + 'lt {
    fn downcast_ref<T : Lifetime_1<'lt>> (&self) -> Option<&T> {
        …
    }
}
…

That way, a type like Foo<'lt> or &'lt (impl 'static) can be dyn-erased to a dyn Any_1<'lt>, whereby we haven't erased that 'lt parameter.

But what about variance? Indeed, the original type might be invariant in the lifetime, so we better not allow changing that one after type erasure. "Luckily", a generic-over-a-lifetime-trait object is invariant (type F<'lt> = dyn Any_1<'lt>; is invariant).

And from there, we get a sound abstraction —albeit a very cumbersome one!— as showcased by the following:

1And what about extending it to more types?

  • I believe we could also implement Lifetime_1<'lt> for something like struct Foo<'lt, T : Lifetime_1<'lt>, U : Lifetime_1<'lt>, …>, which thus allows supporting non-'static type parameters provided they can all be constructed off that one lifetime.

  • We could then extend the _1<'lt> pattern to _2<'a, 'b>, _3<'a, 'b, 'c>, and generic type parameters which would be constructible off exactly those lifetime parameters (or less?);

    • And at that point we realize that impl Lifetime_0 is just impl 'static, and Any_0, Any :slight_smile:

This whole thing could even be made more ergonomic, provided we somehow managed to handle the obvious overlapping cases (using a lot of specialization, I guess) to allow projecting to a single space this "multi-dimensional" construction (e.g., to allow embedding, in a flat manner (without needing a special wrapper type), the 1-generic types within the space of 2-generic types and so on—for the math people, this would be the similar thing, when constructing ℤ as (ℕ x ℕ)/substraction, that allows saying that ℕ ⊂ ℤ rather than ϕ(ℕ) ⊂ ℤ for the trivial ϕ injection):

  • impl<T : Lifetime_0> Lifetime_1<'_> for T
  • impl<'lt, T : Lifetime_1<'lt>> Lifetime_2<'lt, '_> for T
  • etc.
3 Likes

I have no idea how to go about implementing it, but a trait AnyCovariant along these lines seems like it should be both sound and useful:

  • A type T implements AnyCovariant iff it is covariant in all of its embedded lifetime parameters.
  • A dyn 'lt + AnyCovariant value which was originally coerced from a value of type T can be downcast into a value of type T′, where T′ is T with all lifetime parameters replaced with 'lt.

Because the compiler allowed the dyn 'lt + AnyCovariant to be produced, all of the embedded lifetimes must live for at least 'lt anyway, and since they're all covariant, it's sound to replace them with a shorter lifetime (in this case, 'lt).

2 Likes

Yes, that sounds like it should work as well :+1:

  • Proof: it's

    derive_Lifetime_1! {
        struct Wrapper<'lt>(CovariantThing<'lt, 'lt, 'lt, …, 'lt>);
    /* or even:
        struct Wrapper<#[covariant] 'lt>(CovariantThing<'lt, 'lt, 'lt, …, 'lt>); // */
    }
    

    and then funnelling a CovariantThing<'_0, '_1, …, '_n> to a Wrapper<'intersection>