Stuck at lifetimes

help
1

Usually, when I have some lifetimes problem, I can find a workaround. But now I'm stuck.

I need to implement Context object which is mutable and contains a reference to a mutable parent context. Something like this:

struct Context<'a> {
    parent: Option<&'a mut Context<'a>>
}

impl<'a> Context<'a> {
    fn child<'b: 'a>(&'b mut self) -> Context<'b> {
        Context {
            parent: Some(self),
        }
    }
}

Seems legit, type checks fine.

However, I cannot call this child function:

fn this_doesnt_work(context: &mut Context) {
    let mut child = context.child();
}

error is:

13 | fn this_doesnt_work(context: &mut Context) {
   |                              ------------
   |                              |
   |                              these two types are declared with different lifetimes...
14 |     let mut child = context.child();
   |                             ^^^^^ ...but data from `context` flows into `context` here

This makes a little sense to me, so I tried this workaround: specify the same lifetime in &mut and Context. This works:

fn this_doesnt_work<'a>(context: &'a mut Context<'a>) {
    let mut child = context.child();
}

However, this function no longer can be called from a closure:

fn this_doesnt_work_either<'a>(context: &'a mut Context<'a>) {
    (0..10).map(|i| this_doesnt_work_either(context));
}

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter 'a in function call due to conflicting requirements
  --> src/main.rs:18:21
   |
18 |     (0..10).map(|i| this_doesnt_work_either(context));
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime '_ as defined on the body at 18:17...
  --> src/main.rs:18:17
   |
18 |     (0..10).map(|i| this_doesnt_work_either(context));
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:18:45
   |
18 |     (0..10).map(|i| this_doesnt_work_either(context));
   |                                             ^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the function body at 17:28...
  --> src/main.rs:17:28
   |
17 | fn this_doesnt_work_either<'a>(context: &'a mut Context<'a>) {
   |                            ^^
   = note: ...so that the expression is assignable:
           expected &mut Context<'_>
              found &mut Context<'a>

The fun fact is that last snippet works fine when lifetimes are different:

fn this_doesnt_work_either(context: &mut Context) {
    (0..10).map(|i| this_doesnt_work_either(context));
}

So I'm stuck.

  • If I specify the same lifetime in &mut and Context, child function cannot be called from closure.
  • If I don't specify lifetime, then child function doesn't work.

Help?

This code in playground

1 Like
2

&'a mut Context<'a> this (same life) tends to lead to bad outcomes.

struct Context<'a, P> {
    parent: Option<&'a mut P>,
}

impl<P> Context<'_, P> {
    fn child(&mut self) -> Context<Self> {
        Context { parent: Some(self) }
    }
}

fn works<P>(context: &mut Context<P>) {
    let mut child = context.child();
    (0..10).map(|i| works(context));
}
3

Unfortunately, it's not possible to instantiate works function:

fn works<P>(context: &mut Context<P>) {
    let mut child = context.child();
    if true {
        works(&mut child);
    }
}

fn main() {
    works(&mut Context {parent: None::<&mut u32>});
}

error: reached the recursion limit while instantiating `works::<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<Context<u32>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
4

After programming in Rust for a long time, I still don't understand how lifetimes supposed to work.

This snippet looks fine to me:

struct Context<'a> {
    _x: &'a u32,
}

fn x<'a>(_c: &'a mut Context<'a>) {
}

fn y<'a>(c: &'a mut Context<'a>) {
    x(c);
    x(c);
}

8  | fn y<'a>(c: &'a mut Context<'a>) {
   |      -- lifetime `'a` defined here
9  |     x(c);
   |     ----
   |     | |
   |     | first mutable borrow occurs here
   |     argument requires that `*c` is borrowed for `'a`
10 |     x(c);
   |       ^ second mutable borrow occurs here

Playground

5

The reason this doesn't work has to do with variance, see here for details

1 Like
6

I don't understand how it is related to variance, since I'm not trying to assign anything to subtypes or supertypes or reduce or extend lifetimes.

At least, if you are sure it is related to variance

  • which of my examples does not work because of variance?
  • do you know how to fix it?
7

But you are trying to reduce a lifetime. A mut reference can only be given to two different functions one after another if the lifetime given to each is reduced to not overlap.

The answer is to not reuse lifetimes.
fn x<'a, 'b>(_c: &'a mut Context<'b>) { ... }
or more idiomatically
fn x(_c: &mut Context<'_>) { ... }

8

When you try and use a &mut twice, you are reducing its lifetime, and because &mut T is invariant in T you need to have exactly the same lifetime in of the reference as the Context. This condition is broken when you use the &mut twice due to reborrowing.

You must consider variance when the pointee of a pointer can change. Either via a &mut or a Cell or otherwise.

9

yeah, me neither :frowning:

I think what you are trying to achieve is not possible: you are trying to create a stack of values, where all values have the same type and refer to each other. This is fundamentally unsound: if they are of the same type, nothing prevents you from setting the parent of the element at the bottom of the stack to the first element of the stack.

If you make values of different types, you can have constant-depth stacks with Context<'static, 'static, 'static>, Context<'a, 'static, 'static>, Context<'a, 'b, 'static>, Context<'a, 'b, 'c>.

Alternatively, you can say that the parent context has some unknown lifetime, and that you can achive via closures:

struct Ctx<'a> {
    cnt: usize,
    parent: Option<Box<FnMut(&mut dyn FnMut(&mut Ctx)) + 'a>>,
}

impl<'a> Ctx<'a> {
    fn root() -> Ctx<'static> {
        Ctx { cnt: 0, parent: None }
    }
    fn child<'b>(&'b mut self) -> Ctx<'b> {
        Ctx { cnt: 0, parent: Some(Box::new(move |f| f(self))) }
    }
    fn with_parent(&mut self, f: &mut dyn FnMut(&mut Ctx)) {
        if let Some(p) = &mut self.parent { p(f) }
    }
}

fn works(a: &mut Ctx) {
    {
        let mut b = a.child();
        let mut c = b.child();
        c.with_parent(&mut |b| b.with_parent(&mut |a| a.cnt = 92));
    }
    assert_eq!(a.cnt, 92);
}

fn main() {
    let mut ctx = Ctx::root();
    works(&mut ctx);
}

Playground

1 Like
10

I tried this too. See the example "this_doesnt_work_either" in my post.

11

This seems to work fine when stack is created locally:

struct Context<'a> {
    value: u32,
    parent: Option<&'a mut Context<'a>>,
}

fn main() {
    let mut root = Context { parent: None, value: 10 };
    let mut child = Context { parent: Some(&mut root), value: 10 };
    let mut child2 = Context { parent: Some(&mut child), value: 10 };
    child2.parent.as_mut().unwrap().parent.as_mut().unwrap().value = 20;
}

I suspect it is possible to do the same with functions.

I wanted to avoid heap allocation and other runtime overhead (otherwise I could simply do Rc<RefCell>, but thanks for the example!

12

Here is an adapted version of @matklad's example that avoids the heap allocation. The solution is to erase lifetimes with trait objects, but without allocating. playground. This does incur a small cost of using trait objects, but that should be negligable.

13

That actually works! Thank!

14

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.