Apparently equivalent programs do not behave the same

help
1

I had an issue in my code base I didn't understand, so I minimized it to the following (which does not compile)

trait Env<'arena> {
    type Arena;
    fn init() -> Self::Arena;
}

fn eval_arena<'arena, E: Env<'arena>>(_: &'arena E::Arena) {
    todo!()
}

fn eval_bool<E: for<'arena> Env<'arena>>() {
    let arena = E::init();
    eval_arena::<E>(&arena);
}

but turns out that explicitly naming E::Arena apparently makes it work (the following compiles)

trait Env<'arena> {
    type Arena;
    fn init() -> Self::Arena;
}

fn eval_arena<'arena, E: Env<'arena>>(_: &'arena E::Arena) {
    todo!()
}

fn eval_bool<T, E: for<'arena> Env<'arena, Arena = T>>() {
    let arena = E::init();
    eval_arena::<E>(&arena);
}

Why?

4

when you write

trait Env<'arena> {
    type Arena;
    fn init() -> Self::Arena;
}

fn eval_arena<'arena, E: Env<'arena>>(_: &'arena E::Arena) {
    todo!()
}

fn eval_bool<T, E: for<'arena> Env<'arena, Arena = T>>() {
    let arena = E::init();
    eval_arena::<E>(&arena);
}

T is a generic parameter of the function, so the compiler knows values of type T are valid for the whole duration of the function, so when it picks a lifetime for eval_arena it has no problem. it also knows that the T from E::init and eval_arena must be the same no matter the lifetimes.

but consider this

struct MyEvil;

impl<'arena> Env<'arena> for  MyEvil  {
    type Arena = &'arena str;
    fn init() -> Self::Arena  {
        "a"
    }
}

here the type of <MyEvil as Env<'arena>>::Arena depends on the lifetime 'arena,
so the types of E::init and eval_arena could be different. in fact they are only the same if they are called with the exact same lifetime.

so these 2 code examples are actually very different.
i'm not certain yet wether there is a good reason the first doesn't compile, i believe this is just a limitation of the current borrow checker

5

actually @Schard was actually correct, and i do believe the first example should indeed not compile :
consider

struct PrintOnDrop<'a>(&'a str);

impl<'a> Drop for PrintOnDrop<'a> {
    fn drop(&mut self)  {
        dbg!(self.0);
    }
}

struct MyEviler;

impl<'arena> Env<'arena> for  MyEviler  {
    type Arena = PrintOnDrop<'arena>;
    fn init() -> Self::Arena  {
        PrintOnDrop("a")
    }
}

if you call eval_bool<E: for<'arena> Env<'arena>>() on it.

then necessarily the lifetime on init and eval_arena must be the same.

fn eval_bool<E = MyEviler>() {
    let arena : PrintOnDrop<'local> = <MyEviler  as Env<'local>>::init();
    eval_arena::<'local, MyEviler>(&'local arena);
   // arena cannot be dropped here or before because it is still borrowed
   // 'local ends here
   // arena cannot be dropped here or after because the value it holds is invalid
}

the solution @Schard mentionned :

fn eval_arena<'borrow, 'arena: 'borrow, E: Env<'arena>>(_: &'borrow E::Arena) {
    todo!()
}

is probably best.
and you should definitely read &'a Struct<'a> and covariance - Learning Rust

edit : i have found a type that would make this do UB :

use std::cell::Cell;
struct Sketchy<'a> {
  string : String,
  cell : Cell<Option<&'a Sketchy<'a>>>
}

impl<'a> Drop for Sketchy<'a> {
    // if very_dangerous was called on self UB wil happen
    // this can be called by creating a `Sketchy` normally and dropping it
    fn drop(&mut self) {
        let cp = self.cell.get();
        if let Some(other) = cp {
            let other_string : &str = &other.string;
            self.string = String::new(); // deallocate
            dbg!(other_string); // if very_dangerous was called on self this would do use after free
        }
    }
}

// if this is called and the value is dropped UB wil happen
// this can be called safely through Box::leak
fn very_dangerous<'a>(x: &'a Sketchy<'a>) -> &'a Sketchy<'a>{
    x.cell.set(Some(x));
    x
}

and i have found another fix that works without changing eval_arena by making sure drop isn't called.

trait Env<'arena> {
    type Arena;
    fn init() -> Self::Arena;
}

fn eval_arena<'arena, E: Env<'arena>>(_: &'arena E::Arena) {
    todo!()
}


fn eval_bool< E: for<'arena> Env<'arena>>() {
    let mut no_drop_slot : MaybeUninit<E::Arena> = MaybeUninit::uninit();
    let arena = no_drop_slot.write(E::init());
    eval_arena::<E>(arena);
}

proving the destruction is indeed the problem

1 Like
6 
-fn eval_bool<E: for<'arena> Env<'arena>>() {
+fn eval_bool<T, E: for<'arena> Env<'arena, Arena = T>>() {

The key difference is that E::<'arena>::Arena = T must be the same T for every 'arena, i.e. not contain 'arena.

Similarly, this compiles.

-fn eval_bool<E: for<'arena> Env<'arena>>() {
+fn eval_bool<E: for<'arena> Env<'arena, Arena: Copy>>() {

(You may have wanted ManaullyDrop.)

3 Likes
7

Yes, I am aware that this is a dubious pattern in general, but in my case, I really want 'arena = 'borrow, (or at least 'borrow: 'arena) because arena is (as you might have guessed already) a memory arena, and E: Env<'arena> is a type that allocates stuff in in that arena. Since arenas have a signature that looks like alloc(&'a self, v: T) -> &'a mut T, it is enforced that the lifetime of the borrow of the arena is the same as the lifetime of the pointers to objects allocated in it.

This makes a lot of sense! Hence, the patch is actually very easy, without any dirty trick, since I don't want Arena to be able to depend on 'arena:

trait HasArena {
    type Arena;
}

trait Env<'arena>: HasArena {
    fn init() -> Self::Arena;
}

fn eval_arena<'arena, E: Env<'arena>>(_: &'arena E::Arena) {
    todo!()
}

fn eval_bool<E: for<'arena> Env<'arena>>() {
    let arena = E::init();
    eval_arena::<E>(&arena);
}
8

I just found out you can just declare Arena as 'static

trait Env<'arena> {
    type Arena: 'static;
    fn init() -> Self::Arena;
}

Does it fit your use case?

9

This is more restrictive than it needs to be, I think. I don't need Arena to be 'static, I just don't want it to depend on 'arena. Although I have to say that in my use case, this doesn't matter, Arena always ends up being a 'static thing.